Friday 28 July 2017

Playing with Bits

Bit manipulation is a useful technique for solving various problems and can be used to optimize codes and improve its runtime.

The usuals operations in bits are OR, AND,  XOR and NOT. In python we use '|' for OR, '&' for AND, '^' for XOR and '~' for NOT.

Another important operation with bits is shifting. '>>' and '<<' are the arithmetic right and left shift operators. Right shift has the effect of dividing by 2 or a power of 2 and left shift for multiplication by 2 or a power of 2.
E.g.  8 << 2  means 8 multiplied by 2**2 which is (8*4) = 32
        8 >> 2 means 8 divided by 2**2 which is (8/4) = 2

To convert a number from decimal to binary representation in python:
            bin(n)  e.g. bin(7) is '0b111' and bin(7)[2:] gives '111'.
For binary to decimal conversion:
            int(<binary>, 2)    e.g. int('1110', 2) is 14.

Some nice tricks:

  • 1 << x   implies  2**x
          One application where this comes in handy is when we have to implement multiplication without using the '*' operator.
  • (n & (n-1)) == 0 implies n is a power of 2 or 0
          For a number 'n' which is a power of two all bits except the left most bit is 0. So binary representation of of (n - 1) would 
          consist of all 1s.

          E.g For n = 16 , n - 1 = 15 and the binary representations for n and n-1 are '10000' and '1111'.  
          n & (n-1) is '00000' as all the positions of n and n-1 have complimentary bits (i.e. 1s and 0s).

  • n & 1 is 1 if last bit is 1
          This can be used to check if n is odd as the last number being 1 indicates number is odd. The last bit is the bit 
          representing 2**0 which is 1.

          Similarly, n & 1 is 0 if last bit is 0
          If the last bit is 0 then the number is even. So n & 1 == 0 can be used instead of n % 2 == 0.