Bitwise Operations

May 17, 2019 6 minutes

Bitwise algorithms is a class of algorithms where instead of performing common operations like addition, comparisons etc on the decimal numbers, are performed on the individual bits that comprise those numbers.

The bitwise operations are considered very efficient as compared to their decimal counterparts.

Bitwise Operators

Following is the list of bitwise operators:

  • Bitwise AND (&): Performs bitwise AND on the individual bits of the two operands. Reesult of this operation results in a set bit if the two operands were also set (1)and unset (0) otherwise.
  • 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.
  • Bitwise XOR (^): Sets the bit only when the two operand bits were different.
  • Left Shift (<<): Takes two numbers (like a << b) and left shifts the bits of the first operand by the number denoted by second operand.
  • Right Shift (>>): Takes two numbers (like a >> b) and right shifts the bits of the first operand by the number denoted by second operand.
  • 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: $\bbox[yellow]{\lfloor{log_{2}(N)}\rfloor + 1}$
  2. To generate a number with only $i^{th}$ bit set, use $\bbox[yellow]{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 numbner 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: $\bbox[yellow]{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 multiplcation and divison by 2 respectively.
  9. 2’s compliment, used to represent negative numbers = 1’s compliment + 1. Another method of calculating 2’s compliment is to subtract the number from $2^x$ where x is the number of bits used to represent the original number. Example: 2’s compliment 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 compliment of a number N, has all the bits toggled except for the rightmost set bit.

Applications

Here are some usefuly applications of bitwise operatitons:

1. How to check if $k^{th}$ bit is set in a number n or not?

Using LeftShift: 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 righmost 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;

2. How to check if a number is 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 being 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.
3. Brian Kernighan’s Algorithm to check number of set bits in a number.

As seen in 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 above examples, we can see that repeatedly doing an x & x-1 will evantually lead to x being zero in exactly that much 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.

// a utility function to check the number of set bits in number n
int countSetBits(int n){
  int count = 0;
  while (n > 0){
    n &= (n - 1);
    count++;
  }
  return count;
} 
4. How to check the position of 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 compliment with 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.

Examples

Please refer to this link for some related problems solved in java.

comments powered by Disqus