Some Bit manipulation tricks

1. Let's start with a simple one:
n<<1 is equivalent to n*2
More generally:
n<<i is equivalent to n*2ⁱ

Along the same lines:
n>>1 is equivalent to n/2
n>>i is equivalent to n/2ⁱ


2. To find the index of the most significant bit of a number or -1 if 0:
A few examples:
for 3 (11) it is 1
for 121(1111001) it is 6

An algorithm for this involves iterating the bits of a number and looks something like this in java - essentially keep right shifting until the value is 0:

int findIndexOfMostSignificantBit(int n){
       int s=0;
        while(n!=0){
            s++;
            n = n >> 1;
        }
        return s>0?s-1:-1;
    } 

3. Multiply two numbers using bit manipulation:
I look at it this way:
a*b with b represented in binary can be thought of as a*(x*2^0 + x*2^1....x*2^n),

int multiply(int a, int b){
     int sum = 0;
     for (int i=0;b!=0;i++){
      if((b&1)!=0){
       sum += (a<<i);
      }
      b = b>>1;
     }
     return sum;
    }

4. What does (n &(n-1))==0 mean?
Well, it is a way to check if a number can be represented as a power of 2 -
eg 8&7 becomes 1000 & 0111 which is 0, 7 & 6 becomes 0111 & 0110 which is NOT 0

5. Getting a bit at index i:

(n & (1<<i))!=0

6. Setting a bit at index i:

n=n|(1<<i)

7. Clearing the bits between index i and j:
A sample for this is 121(1111001) clear bits between 4 and 2 yields in binary 1100001

The trick here is to create a mask which is all 1's except between i and j:
this mask can be created in two parts, the right part of the mask is created by left shifting 1 j places and subtracting 1 which results in all the bits from 0 to j-1 being set with 1.

the left part of the mask is created by negating 0 which yields all 1's, followed by shifting left i+1 places which puts 0's upto ith place.

int clearBits(int n, int i, int j){
    int left = (~0)<<i+1;
    int right = (1<<(j))-1;
    
    return n&(left|right);
}