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.

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.

How it works

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



Related Contents to follow