Bitwise Operators

In this section, we will discuss different bitwise operators available and used in Java and then we will discuss some of the algorithms and tricks to solve problems using a bitwise operator. We will try to understand each operator with the help of examples.

1. AND Operator (&)

Let say there are two numbers x = 2 and y = 3. Then if we try to find  (x & y), it will return 2 i.e. (2 & 3) = 2. Now let's try to understand, how it becomes 2. 

If we will run AND(&) operator between two numbers then it checks its binary form and only returns 1 in case both the bits are 1, or else it will return 0, which means if we convert 2 and 3 to there binary form then it will return us 010 which is 2 in decimal form.
 

2	0	1	0
3	0	1	1
Result	0	1	0

If we will observe closely, it returned us 1 only when both the bits were 1, in every other case, it returned us 0.

2. OR Operator (|)

Next is the OR operator. Let us we have the two numbers again i.e. x = 2 and y = 3 and if we try to find (x | y), it will return us 3 i.e. (2 | 3) = 3.

If we run OR(|) operator for any two numbers then it checks each bit of the number in its binary form and returns 1 if any bit is 1. It only returns 0 in case both bits are 0. In this case, it will check each bit based on the below table and will return us 011 i.e. 3

2	0	1	0
3	0	1	1
Result	0	1	1

In this case, if we observe closely, it returned us 1 even if anyone bit is 1 and it only returned 0 when both the bits were 0.

3. COMPLEMENT Operator (~)

If we run complement operator on any number then it will reverse each bit of the number in its binary form i.e. if the binary form of any number is 10101 and if we have executed ~ operator then it will return us 01010. 

For Ex: If we have a number x = 2 the (~x) = 5 i.e. (~2) = 5. Let's try to understand this with the help of the below table:

2	0	1	0
Result	1	0	1

If we observe closely, then we will notice that all the bits which were 0 have been converted to 1 and all the bits which were 1 have been converted to 0 after running a complement operator.

4. XOR Operator (^)

This operator is executed between two numbers and it checks each bit of the binary form of the numbers and returns 0 if both the bits are same and 1 if both the bits are different.
For Example, if we have two numbers i.e. x = 2 and y = 3 then (x^y) = 1 i.e. (2^3) = 1. Lets try to understand with the help of below table:

2	0	1	0
3	0	1	1
Result	0	0	1

If we observe closely, the xor operator returned 1 when both the bits were different and return 0 when both the bits were same.

Some interesting observation for xor operator:

• x^0 = x
• x^y = y^x
• (x^y)^z = x^(y^z)
• x^x = 0

5. Right Shift Operator (>>)

This operator is executed between two numbers and the bits of the first number are right-shifted by the number of times the second number.

For Ex: If we have two numbers i.e. x = 5 (101) and k = 2. Then if we try to find (x>>k), we need to right shift bits of x by k positions i.e. (101) will become (1) which means the last two bits (01) of x were dropped.

Observation: If we right shift x by k i.e. (x>>k) then the result will be equivalent to x/2^k

6. Left Shift Operator (<<)

<sup>This operator is again executed between two numbers and the bits of the first number are left-shifted by the number of times the second number.
For Ex: If we have two numbers i.e. x = 5 (00101) and k = 2. Then if we try to find (x<<k), we need to left-shift bits of x by k positions i.e. (...0000101), will become (10100) = 20 which means the last two bits (00) of x were shifted to the right.
In this case, we have taken  5 as ...0000101 in binary form and not 101 as in this case the left digits matter to us as we need to shift it by k positions.

Observation: If we left shift x by k i.e. (x<<k) then the result will be equivalent to x*2k</sup>

Some tricks which can help in problem-solving:

1. If we need to generate a number with the only kth bit set as 1 and rest all bit as 0, then we can use the below formula: 

(1 << (k-1))

2. If we have a number n and need to calculate 2n, then we can use the below formula:

1 << n

3. If we need to check if any number n is the power of 2 or not then we can use the below formula:

(n & (n-1))

If the above expression returns 0, then it is the power of 2, or else it is not the power of 2.
The above expression is also used in Brian Kernighan's Algorithm to check the number of set bits. Check it out on the web.