Reversing XOR and Bitwise operation in Python

That's Gray code. There's also a chapter about it in Hackers' Delight. There's some code in that wikipedia article, but to avoid a link only answer, here's how you construct the inverse:
do x ^= x >> (1 << i) for i = 0 .. ceil(log_2(bits)) - 1.

So for 32 bits integers,

x ^= x >> 1; x ^= x >> 2; x ^= x >> 4; x ^= x >> 8; x ^= x >> 16; 

For n-bit integers: (not fully tested, but seems to work so far)

def gray2binary(x): shiftamount = 1; while x >> shiftamount: x ^= x >> shiftamount shiftamount <<= 1 return x 

For a much faster version of the conversion see @harold's answer.

Let's consider 2-bit numbers:

00 = 00 ^ 00 (0 -> 0) 01 = 01 ^ 00 (1 -> 1) 11 = 10 ^ 01 (2 -> 3) 10 = 11 ^ 01 (3 -> 2) 

If y[i] is i-th bit (little-endian) then from y = x ^ (x >> 1) follows:

y[1]y[0] = x[1]x[0] ^ 0x[1] # note: y[1]y[0] means `(y[1] << 1) | y[0]` here 

It means that:

y[1] = x[1] ^ 0 y[0] = x[0] ^ x[1] 

If we know y then to get x:

 y[i] = (y & ( 1 << i )) >> i x[1] = y[1] ^ 0 x[0] = y[0] ^ x[1] = y[0] ^ (y[1] ^ 0) x = (x[1] << 1) | x[0] 

You can generalize it for n-bit number:

def getbit(x, i): return (x >> i) & 1 def y2x(y): assert y >= 0 xbits = [0] * (y.bit_length() + 1) for i in range(len(xbits) - 2, -1, -1): xbits[i] = getbit(y, i) ^ xbits[i + 1] x = 0 for i, bit in enumerate(xbits): x |= (bit << i) return x 

y2x() could be simplified to work with numbers without the bit array:

def y2x(y): assert y >= 0 x = 0 for i in range(y.bit_length() - 1, -1, -1): if getbit(y, i) ^ getbit(x, i + 1): x |= (1 << i) # set i-th bit return x 

Example

print("Dec Gray Binary") for x in range(8): y = x ^ (x >> 1) print("{x: ^3} {y:03b} {x:03b}".format(x=x, y=y)) assert x == y2x(y) 

Output

Dec Gray Binary 0 000 000 1 001 001 2 011 010 3 010 011 4 110 100 5 111 101 6 101 110 7 100 111