Reversing XOR and Bitwise operation in Python

Question

I tried searching a lot but I am not able to find a solution to reversing XOR and Bitwise operation combined.

num[i] = num[i]^( num[i] >> 1 );

How can I reverse this operation using Python. I tried the XOR concept explained here: What is inverse function to XOR?

Still unable to solve the math.

Answer 1

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