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.

XOR is a binary operator. It needs two operands to work. To reverse the effect of it, you need atleast two operands. But you have only one operand. So, there will be many combination of numbers which could have produced the result. — thefourtheye, Oct 21 '14 at 08:47
@thefourtheye: [the formula can be reversed](http://stackoverflow.com/a/26482800/4279) — jfs, Oct 21 '14 at 09:02

harold · Answer 1 · 2014-10-21T09:43:49.997

7

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

edited Oct 21 '14 at 09:43

answered Oct 21 '14 at 09:23

harold

61,398
6
86
164

+1 for recognizing Gray code. You should add a small Python snippet that works for arbitrary precision Python integers. – jfs Oct 21 '14 at 09:34
@J.F.Sebastian ok I can try, I don't know much Python though – harold Oct 21 '14 at 09:39
I've added code example. You could replace it with your code. – jfs Oct 21 '14 at 09:40
@J.F.Sebastian ok thanks, it should be possible to make it run in logarithmic time too – harold Oct 21 '14 at 09:40
I've measured time performance on the Gray code of 30-th Mersenne prime (`p = 2 ** 132049 - 1`). Your code is 1000x times faster (731ms vs. 280 µs). – jfs Oct 21 '14 at 09:55

score 3 · Answer 2 · edited May 23 '17 at 11:59

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

Reversing XOR and Bitwise operation in Python

2 Answers2

Example

Output