Some important tricks with bits that you need to remember

1. Divide by 2:

x>>=1

2. Multiply by 2: 

x<<=1

3. Clear the lowest set bit for x:

x & (x-1)

4. Extracting the lowest set bit of x.

x & ~(x-1)   

5. Clearing all bits from LSB to i’th bit.

bitmask = ~((1 << i+1 ) - 1);
x & = mask ;

6. Clearing all bits from MSB to the i’th bit.

bitmask = (1<<i)-1;
x & = mask ;

7. A number x with lowest cleared bit set.

x | (x + 1)

8. Extracts the lowest cleared bit of x.

x | ~(x + 1)

8. Checking if a number x is a power of 2 or not.

if (x && !(x & (x-1) ) )==1
then x is a power of 2.

Example 1:

Checking if the given number is a power of 2.

A very simple solution for this would be to divide the given number by 2 until it is even. If the remaining number is 1 then it is a power of 2 otherwise not a power of 2.

int PowerOfTwo(int n) { if(n==0) { return false; } else { while(n % 2 == 0) { n/=2; } if(n==1) return true; else return false; } }

def PowerOfTwo(n): if n==0: return False else : while n % 2 == 0 : n = n / 2 if n==1 : return True else : return False 

class PowerOfTwo { public static int powerOfTwo(int n) { if(n==0) { return false; } else { while(n % 2 == 0) { n/=2; } if(n==1) return true; else return false; } } }

Example 2:

Finding the x^y in O ( logn ).

This algorithm is one of the most important algorithms in computer science. It is known as the Binary Exponentiation .  The basic idea is that we can represent y in terms of powers of 2 ( Example  y= 13 = 2^3 + 2^2 + 2^1 ) , and now we can write x^y as x^(2^a) * x^(2^b) * ….
Where a, b .. are set bits of y.

An important observation here is that we only need x^(power of 2) , so we can find all x^(2^a) for all a<=63 (as 2^63 is equal to 10^18 and y can only be upto 10^18)  which can be done in O( log y ) and then multiply it to the answer if a is a set bit of y.

As x^y would become very large for some large numbers ( Example 20 ^ 30 ) , instead of finding x^y we would find (x^y) % mod , where mod is a large prime number.

int power(int x,int y,int mod) { int ans=1; while(y) { if(y%2) { ans=(ans*x)%mod; } y=y>>1; x=(x*x); } return ans; }

def power(x,y,mod): ans=1; while y>0 : if y%2 != 0 : ans=(ans*x)%mod y=y>>1 x=x*x return ans 

class BinaryExponentiation { public static int power(int x,int y,int mod) { int ans=1; while(y>0) { if(y%2 != 0) { ans=(ans*x)%mod; } y=y>>1; x=(x*x); } return ans; } }

Examples 3:

Finding the number of set bits of a number.

We are going to use the property ( x & (x-1) ) , which clears the lowest set bit.

int CountSetBits(int x) { int cnt = 0; while (x) { x &= (x-1); cnt++; } return cnt; }

def CountSetbits(x): cnt=0 while (x) : x = x & (x-1) cnt=cnt+1 return cnt 

Jclass CountSetBits { public static int countSetBits(int x) { int cnt=0; while(x) { x= x & (x-1); cnt++; } } }

Example 4:

Checking if the i’th bit is set in the given number x.

When the i’th bit is set in the given number x , then (x&(1<<i)) has to be (1<<i) . ( Here (1<<i) is equal to 2^i ) . This is because (1<<i) has only the i’th bit set. By taking the AND of x with (1<<i) we just check if x has the i’th bit set or not.

bool ithBitSet(int x , int i) { if(x&(1< 

def ithBitSet(n): if x & (1< 0 : return True else : return False

class IthBitSet { public static int powerOfTwo(int x) { if(x&(1< 

Example 5:

Finding all subsets of a given array. 

We can represent each element in the array as a bit . As we know there are 2^n subsets of an array of size n. So we can iterate i from 0 to 2^n-1 and for each number we can check which bits are set i.e. if the j’th bit of a particular number is 1 then the i’th element would be present in that subset . Let us take one example to understand this more clearly .

Let us say that the array is [ 1 , 2 , 3 ] .

As the size of the array is 3 , we can iterate i from 0 to 2^3-1 i.e from 0 to 7. 

void find_subsets( int arr[] , int n ) { for ( int i=0 ; i < pow(2,n) ; i++) { for(int j=0 ; j < n ; j++) { if((i&(1< 

def find_subsets( arr , n ) for i in range(0,1< 

class Subsets { public static void find_subsets( int arr[] , int n ) { for ( int i=0 ; i < pow(2,n) ; i++) { for(int j=0 ; j < n ; j++) { if((i&(1<