Bit Manipulations

Basic bitwise operations: 

&   -  bitwise and
|   -  bitwise or
^   -  bitwise xor
~   -  bitwise not
<<  -  bitwise shift left
>>  -  bitwise shift right

various bit operations problems:

1. check odd or even integer:

[code]
    (x & 1) == 1 // is odd else even

2. check the n-th bit is set or not:

[code]
    (x >>n ) &  1 == 1 // is set else not set

3. set the n-th bit:

[code]
    x | (1<<n)

4. unset the n-th bit:

[code]
    x & ~(1<<n)

5. toggle the n-th bit:

[code]
    x ^(1<<n)

6. turn off the rightmost 1-bit:
For example, given an integer 00101010, it turns into 00101000.

[code]
    x & (x-1)

7. isolate the rightmost 1-bit:
For example, given an integer 01010100, gets value: 00000100.

[code]
    x & (-x)

8. right propagate the rightmost 1-bit:

Given a value 01010000 turns into 01011111. All the 0-bits right to the right most 1-bit get turned into ones. 

[code]
    x | (x-1)

9. Isolate the rightmost 0-bit:

For example, this number 10101011, producing 00000100.

[code]
   ~x & (x+1)

10. Turn on the rightmost 0-bit:

For example, given an integer 10100011 turns into 10100111.

[code]
   x | (x+1)

11. Implement addition using only bitwise operators:

[code]
int BitAdd(int a, int b)
{
    int carry = a & b;
    int result = a ^ b;
    int shiftcarry;
    while (carry != 0) {
        shiftcarry = carry << 1;
        carry = result & shiftcarry;
        result = result ^ shiftcarry;
    }
    return result;

}
 

12. Implement subtraction using only bitwise operators:
Based on the previous function BitAdd(), we have,

[code]


int BitSub(int a, int b)   // a - b
{ 
     int nb = BitAdd(~b, 1);    // b --> -b
     return BitAdd(a, nb);      // a-b = a+ (-b)
  
}
 

13. Implement multiplication using only bitwise operators:

[code]

int BitMul(int a, int b)
{
        bool isNeg = (a > 0) ^ (b > 0);
        unsigned int x = a > 0 ? a : BitAdd(~a,1);
        unsigned int y = b > 0 ? b : BitAdd(~b,1);
        int ans = 0;
        while (y)
        {
                if (y & 0x01) ans = Add(ans, x);
                y >>= 1, x <<= 1;
        }
        return isNeg ? BitAdd(~ans, 1) : ans;
}

14. Implement division using only bitwise operators:

[code]

int BitDiv(int a, int b)   // b !=0
{
        bool isNeg = (a > 0) ^ (b > 0);
        unsigned int x = a > 0 ? a : BitAdd(~a,1);
        unsigned int y = b > 0 ? b : BitAdd(~b,1);
        int ans = 0;
        for (int i = 31; i >= 0; i--)
            if ((x >> i) >= y) {     //x >= (y << i) // avoid overflow
               x = BitSub(x, y << i),
               ans = Add(ans, 1 << i);
             }
        return isNeg ? BitAdd(~a,1) : ans;
}
                              

15. Implement a to the power of b using bitwise operators:

[code]

int BitPow(int a, int b)
{
        int ans = 1, q = a;
        while (b)
        {
                if (b & 0x01) ans = BitMul(ans, q);
                b >>= 1;
                q = BitMul(q, q);
        }
        return ans;
}
                     

16. Swap odd and even bits in an integer (eg. bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped):

[code]

int OddEvenBitSwap(int x)
{
   return ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)
}
                     

17. Check if binary representation of a number is palindrome. Given an integer ‘x’, write a C function that returns true if binary representation of x is palindrome else returns false.

[code]

bool ispan(int x)
{
     int p = x;
     int r = 0;

     while(p){
         r = (r<<1) | (p & 0x01);
         p = p >> 1;
     }
     return !(r ^ x);
}
                     

Another way to do it is to one by one compare the most significant bit against the least significant bit.

[code]

bool ispan(int x, int length)
{
     int p = length -1;
     int r = 0;

     while(l>0){
         if( ((x>>l) & 1 ) != ((x >>r) & 1)) return false;
         l --; r ++;
     }
     return true;
}                     

(LintCode) Given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M (e g , M becomes a substring of N located at i and starting at j)

[code]
int bitupdate(int n,  int m, int j, int i)
{
      int mask = (((1 << (j+1)) -1) ^ ( (1<<(i)) -1));
      m = m << i;
      n = n & (~mask);
      n = n | m;
      return n;
}

                     

Using O(1) time to check whether an integer n is a power of 2.

[code]
bool checkpowerof2(int n)
{
      return (n & (n-1)) == 0;
}

                     

Count how many 1 in binary representation of a 32-bit integer.

[code]
bool bitcount(int n)
{
      int count = 0;
      while(n!=0) {
         n = n &(n-1);
         count ++;
      }      
      return count;
}

Determine the number of bits required to flip if you want to convert integer n to integer m.

[code]
bool bitflipnum(int n, int m)
{
      int count = 0;
      n = n ^ m; 
      while(n!=0) {
         n = n &(n-1);
         count ++;
      }      
      return count;
}

A RGB Conversion:

Given a 16-bit integer RGB code, the bit maps are as follows:  

Code = 5(R-bits)6(G-bits)5(B-bits)

Convert it into three 8-bit RGB codes.

Solution:

   1)using bit shift and mask operations to extract each color code;

   2)calculation each scale from 31 (2^5-1) or 63 (2^6-1) to 255 (2^8-1); 

   3)forming a new 24bit RGB code;