在Python中反转XOR和位运算

Question

我搜索了很多，但还是找不到解决方法来反转结合了XOR和位运算的操作。

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

我想知道怎么用Python来反转这个操作。我试过这里解释的XOR概念：XOR的反函数是什么？

但还是无法解决这个数学问题。

Answer 1

如果你想要一个更快的转换方法，可以看看 @harold的回答。

---

我们先来看看2位数字：

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

如果 y[i] 是第i位（小端格式），那么根据 y = x ^ (x >> 1) 可以得出：

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

这意味着：

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

如果我们知道 y，那么要得到 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]

你可以把这个方法推广到 n 位数字：

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() 可以简化为直接处理数字，而不需要位数组：

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

示例

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)

输出

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

Answer 2

这就是格雷码。在《黑客的快乐》一书中也有一章专门讲这个。维基百科的文章里有一些代码，不过为了避免只给链接的回答，这里告诉你怎么构造它的反向：
对每个从0到ceil(log_2(位数)) - 1，执行x ^= x >> (1 << i)。

所以对于32位整数，

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

对于n位整数：（虽然没有完全测试，但目前看起来是有效的）

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