Some important tricks with bits that you need to remember
1. Divide by 2:
2. Multiply by 2:
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.
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.
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.
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.
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.
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.