Bitwise Operators

Bitwise operators are used in a class of algorithms where instead of performing common operations like addition, comparisons, etc on the decimal numbers, those are performed on the individual bits that comprise those numbers. The bitwise operations are considered very efficient as compared to their decimal counterparts.

Following is the list of bitwise operators:

1. Bitwise AND (&): Performs bitwise AND on the individual bits of the two operands. The result of this operation results in a set bit if the two operands were also set (1)and unset (0) otherwise.

2. Bitwise OR (|): Used to perform OR operation on individual bits of the two operands. The resultant bit is set if either of the two operand bits was set and zero otherwise.

3. Bitwise XOR (^): Sets the bit only when the two operand bits were different.

4. Left Shift («): Takes two numbers (like a « b) and left shifts the bits of the first operand by the number denoted by the second operand.

5. Right Shift (»): Takes two numbers (like a » b) and right shifts the bits of the first operand by the number denoted by the second operand.

6. Bitwise NOT (~): A unary operator, bitwise NOT is used to flip all the bits of the operand number.

Examples

• 5(101) & 3(011) = 1(001)
• 5(101) | 3(011) = 7(111)
• 5(101) ^ 3(011) = 6(110)
• 5(101) « 2 = 20(10100)
• 5(101) » 2 = 1(001)
• ~5(101) = 2(010)

Some Tips

1. The number of bits used to represent a number in binary notation is given by: \({\lfloor{log_{2}(N)}\rfloor + 1}\)

2. To generate a number with only \(i^{th}\) bit set, use \(1 « (i-1)\); This will shift the only set bit in 1 to i positions to the left.

3. To set the \(i^{th}\) bit of a number N, do a binary OR (i.e. |) of the number N with the output of tip 2.

4. To clear the \(i^{th}\) bit of a number N, the idea is to first generate a number with \(i^{th}\) bit cleared and then doing binary and of this generated number with the original number. To generate the said number (with \(i^{th}\) bit cleared), we can negate the output of tip 2 and can then use the result to do & operation. In short, the same is equivalent to: \({N \& \sim(1 « (i-1))}\)

5. To toggle the \(i^{th}\) bit of a number N, do a binary XOR (i.e. ^) of the number N with another number having only \(i^{th}\) bit set (output of tip 2).

6. All power of two numbers have only one bit set. Example: 2(010), 4(100), 8(1000) and so-on.

7. The & operator can be used to check if a number x is even or odd. For all even x, x&1=0 and 1 otherwise. Example: 2(010) & 1(001)= 0; 6(110) & 1(001) = 0, 3(011) & 1(001) = 1

8. « and » are equivalent to multiplication and division by 2 respectively.

9. 2’s complement, used to represent negative numbers = 1’s complement + 1. Another method of calculating 2’s complement is to subtract the number from \(2^x\) where x is the number of bits used to represent the original number. Example: 2’s complement of 5(101) = ~(101) + 1 = (010)+1 = 011 = 3; The same can also be calculated using \(2^3-5=3\); as here x=3 represents 3 bits used for 5.

10. 2’s complement of a number N, has all the bits toggled except for the rightmost set bit.

Applications

Here are some useful applications of bitwise operations:

How to check if \(k^{th}\) bit is set in a number n or not?

Using Left Shift: As we know that only 1 bit is set for number 1, and shifting it left by k-1 units will give a number having only \(k^{th}\) bit set. We can use it to find if \(k^{th}\) bit is set in a number or not by doing a bitwise AND on this calculated number and the original number.

A non-zero result will denote that the bit is set: return (n & (1« (k - 1)) >= 1) ? true : false;

Using RightShift: As right shifting a number drops the lower order bits, to see if \(k^{th}\) bit is set for a number or not, we right-shift it by k-1 positions so that the \(k^{th}\) bit is now the rightmost bit. The only task now left is to do a bitwise and of this result with 1 which will be non-zero if the bit was already set: return (1 & (n » (k - 1)) >= 1) ? true : false;

1. How to check if a number is a power of 2 or not?

As mentioned above, any power of 2 will have only 1 bit set in its binary representation like 2(010), 4(100), 8(1000), and so on. Also, it can be observed that subtracting 1 from any number (which is a power of 2) will lead to:

• All the bits after the only set bit, being set.
• The only set bit is unset.

For Example:

• \(4(100) \rightarrow 3(011)\)
• \(8(1000) \rightarrow 7(0111)\)

From the examples mentioned above, we can observe that:

• n & (n-1) = 0; if n is power of 2
• \(\ne 0\) otherwise.

2. Brian Kernighan’s Algorithm to check the number of set bits in a number

As seen in the above examples, subtracting 1 from a number (say x) will toggle all bits from right to left until the first set bit, and thus performing an & between x&(x-1) will unset the rightmost set bit.

Example:

• 5(101) & 4(100) \(\rightarrow\) 4(100)
• 4(100) & 3(011) \(\rightarrow\) 0(000)

As clear from the above examples, we can see that repeatedly doing an x & x-1 will eventually lead to x being zero in exactly that many iterations as is the number of set bits. This is due to the fact that in every iteration, the rightmost set bit is being unset.

3. How to check the position of the rightmost set bit in the binary representation of a number?

1. Take 2’s complement of the given number (say N) as it will have all bits as reverted except the first set bit from right to left.

2. Do a bit-wise & of 2’s complement with the original number. The result will have only 1-bit set which will be the rightmost set bit in the original number i.e. calculate N & -N.

3. Calculate \({log_{2} (N \& -N)}\), this will give you \({position-1}\), where position is the location of first set bit from RHS.

4. Add 1 to the output of step 3.