Bit Operation

Bit Operation Essential Things

For details about Bit, this blog is helpful.

For my revise :)

1. Left Shift ( << ) means multiply a number by 2, or, some powers of 2.
   Approach : a<<2   where a = 1011101
   after operation                 a = 1110100
2. Right Shift ( >> ) means divide a number by 2 or powers of 2.
   Approach : a>>2   where a = 1011101
   after operation                 a = 0010111
3. Precedence of Bit Operator
   NOT ( ~ ) highest
   AND ( & )
   XOR ( ^ )
   OR ( | ) lowest
4. Is a power of 2?
   

     bool isPowerOfTwo(int x)
       {
           // x will check if x == 0 
           // and !(x & (x - 1)) will check if x is a power of 2 or not
           return (x && !(x & (x - 1)));
       }

5. Count the number of ones in the binary representation of the given number..
   

       int count_one (int n)
           {
               while( n )
               {
               n = n&(n-1);
                  count++;
               }
               return count;
       }

6. Check if the ith bit is set in the binary form of the given number
   

    bool check (int N)
       {
           if( N & (1 << i) )
               return true;
           else
               return false;
       }

7. Swap two integers without using any third variable
   Let A = 5 and B = 6
   A = A ^ B = 3     /* 101 XOR 110 = 011 */
   B = A ^ B = 5     /* 011 XOR 110 = 101 */
   A = A ^ B = 6     /* 011 XOR 101 = 110 */
   So, A = 6 and B = 5
8. Divisibility by power of 2
   
   Here, P is in the form 2^X and N is an integer (typically unsigned)

   N % P = N & (P-1)
   N / P = N >> X
   N * P = N << X

   
   About the % operation: the above is possible only when P is a power of 2
9. Clear all the SET BIT without the Least Significant Bit of a number N.
   

     N = N & -N; 

10. Find the position of MSB(Most Significant Bit)
     int position = log2(N);