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.

Reversing Shift-XOR operation

Reversing Shift-XOR operation (when XORed with the same value)

The random number generator Mersenne Twister uses 624 internal states, each 32 bits, to generate the random numbers. If the internal states are known then the random numbers can be predicted. The major step involved in obtaining the random number from the internal states are a series of shift-XOR operations. If these operations are inverted, then the internal states can be found from the random numbers.

'>>' is the right shift operator (adds zeros to the left/MSB side) and '<<' is the left shift operator. '^' is the XOR operator.

Below the process involved in reversing a right shift-XOR operation is explained.

Let n = 3008349343, the shift value is 10 and (n ^ n >> 10) = 3009615726.

In binary :

10110011010011111100010010011111      n

00000000001011001101001111110001      n >> 10

10110011011000110001011101101110      n ^ n >> 10

From the above operations we can see the first 'shift'(=10 here) number of bits remain the same as it is XORed with 0's. Let us consider compartments of size 10; for a 32 bit number we have 3 compartments of size 10 and one of size 2.

The shifting operation and the reversing of the shift is diagrammatically represented in the figure below.

Thus, given the value 3009615726 and the shift value 10, we can reverse the shift-XOR operation to obtain 3008349343.

The same approach can be adopted for any shift value and for reversing the left shift-XOR operation also. The compartments size vary depending on the shift value.

The code for reversing the shift-XOR operations: 

https://gist.github.com/PhoeniXkrypT/22b978dee79f3092d63f