**1. Let's start with a simple one:**

n<<1 is equivalent to n*2

More generally:

n<<i is equivalent to n*2

^{i}

Along the same lines:

n>>1 is equivalent to n/2

n>>i is equivalent to n/2

^{i}

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

## No comments:

## Post a Comment