# Advance uses of bit manipulation in competitive programming

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.*

- http://wikistack.com/traveling-salesman-problem-dynamic-programming/
- 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.*

## Leave a Reply