Bitwise Operator 

The computer programming that we do, by writing thousands of lines of code to create all the complex, great apps, software, games; Search engines like Google, Bing or our country's ants or sparrows have something extraordinarily powerful at the root of everything: bit: 0 and 1. The numbers (int, double, float, long long) and the characters (char, string) that we write are all stored on the computer with 0, 1. These bits are used to perform a variety of tasks, such as low-level device control, data compression, encryption, networking, etc.! Any kind of operation with bits is called bit manipulation in the language of programming.


Bitwise Operation is the heart of Bit Manipulation. As a programmer we always have clear idea about bitwise operators and how they works. There are 6 (six) basic operators. They are - 

  • AND ( & )
  • OR ( | )
  • XOR ( )
  • NOT ( )
  • LEFT SHIFT ( << )
  • RIGHT SHIFT ( >> )

AND, OR, XOR : These operators works with the same length bit patterns. Let's see the basic core thing what they do !

AND : If the two bits are 1 and the operation will be AND, the answer will 1 . Otherwise it will be 0 .
OR : From the two bits if one bit is 1  or two bits are 1, the OX operation answer will 1 . Otherwise 0 .
XOR : If the two bits are 0, the answer of XOR operation will 0 . Otherwise 1 .
NOT : This operator flips any bit, that is, if it is 1, answer will 0 and if it is 0, answer will 1 .

AND OR XOR NOT


Left or Right Shift means they shift bits in a bit pattern to left or right position.

Left shift to any number by k bit means multiplied by 2k
1 << 1 = 2 = 21
1 << 2 = 4 = 22
1 << 3 = 8 = 23
1 << 4 = 16 = 24
1 << n = 2n

On the other hand, right shift to any number by k bit means divided by 2k .
4 >> 1 = 2
6 >> 1 = 3
5 >> 2 = 1
16 >> 3 = 2

Let's see some easy example with 8 bit binary representation with left and right shift.

In Left shift suppose we have 1 0 0 1 1 0 0 1 and we want to left shift 2 bit. 
The answer will  0 1 1 0 0 1 0 0 . Here delete 2 bits from the front and add 2 zero bit ( 0 ) to back.
1 0 0 1 1 0 0 1 << 2  =  0 1 1 0 0 1 0 0

And the opposite things happen in Right shift. we have again 1 0 0 1 1 0 0 1 and we want to right shift 2 bit. the answer will 0 0 1 0 0 1 1 0.
1 0 0 1 1 0 0 1 >> 2  =  0 0 1 0 0 1 1 0

Left shift and Right shift

Bitwise operations work very fast and efficient and so to optimize time, bit manipulation is useful.
Now we know about some problem and algorithms that will be done by bit manipulation.

Checking whether a number is power of 2

If we think normally, firstly we check if the number is an even number, then it will be divided by 2 until we get 1. Then we will count and find the power of 2. But this time complexity will O ( log n ). On bit manipulation, we optimize it to O ( 1 ) means constant time complexity. See how,

Let, need to find X is a power of 2. we will do AND operation between X and ( X - 1 ) and if the result is equal to  Zero ( 0 ), we can say X is a power of 2.
X & ( X - 1 ) = 0

Let, X = 4 , so X - 1 = 3 .
4 = (100)2   and   3 = (011)2
100 & 011 = 000. Prove, 4 = 22

Your work is to prove 9 is a power of 2 or not ?
Program Code :
 
bool isPowerofTwo ( int x )
{
    return x && (!(x&(x-1)));
}



Post a Comment

Previous Post Next Post