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.

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

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

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

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