In this blog post we will discuss some advance uses of bit manipulation in competitive programming. Kindly follow my previous two blog post for some basic refresh. (1) bit-manipulation-in-c (2) Some uses of bit manipulation in c or c++ programming .

some advance uses of bit manipulation

check whether the number is power of 2

Given a positive number n, write a program to check whether the given number is power of 2 or not. suppose given number is 8,then your program should return yes. If the given number is 7 ,then your program should return NO.

#include<stdio.h>

int main() {

	int n = 8;
	printf("Enter a positive number to check \n");
	scanf("%d", &n);

	// check power of 2
	if (n && (n & (n - 1)) == 0) {
		printf("YES\n");
	} else
		printf("NO\n");

	return 0;
}

How it works

  • Any positive number which is power of two has only one bit set. For example binary equivalent of 4 is 100, binary equivalent of 8 is 1000 etc.
  • Let us subtract 1 from number 4 , so after subtraction it will be 3.
  • Binary equivalent of 3 is 0110.
  • bitwise & of 1000 and 0110 ( 1000 & 0110 ) becomes 0.
  • So if a number will be power of 2, then expression number & (number -1 ) becomes always zero.

Solving traveling sales man problem using bit manipulation.

  1. http://wikistack.com/traveling-salesman-problem-dynamic-programming/
  2. http://wikistack.com/what-is-power-set-with-example/

Count the number of one’s

Given a positive number count the number of one’s in it.

#include<stdio.h>

int main() {

	int n = 0;
	printf("Enter a positive number to check \n");
	scanf("%d", &n);
    int count=0;
	// count one's
	while (n) {
		n = n & (n - 1);
		count++;
	}
	printf("The number of one's is %d\n", count);
	return 0;
}

How it works

  • Try to toggle using expression n & ( n – 1) , while it becomes zero.


Related Contents to follow