## Saturday, March 24, 2012

### Some Bit manipulation tricks

n<<1 is equivalent to n*2
More generally:
n<<i is equivalent to n*2i

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

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);
}
```