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<