自异或性质笔记

发表于 本文字数： 1.2k 阅读时长 ≈ 1 分钟
有关自异或性质的简要笔记

自异或简述

自异或指的是一系列数值本身与自身进行异或的算法，例如存在 \[ A\oplus A=0 \] 也算是一种算法。

但本文只讨论一些需要推理过程的自异或逆算法。

自位移异或

自位移异或指的是形如 \[ A\oplus (A>>bit) \] 的算法。

简单起见，我们观察一个 8 位二进制数，右移 3 位后异或的过程。

1
2
3
value:    1101 0010
shifted:  0001 1010 # 010 (>> 3)
result:   1100 1000

首先，观察到 result 的最高 shift 位与 value 的最高 shift 位是一样的。因此，在 result 的基础上，我们可以将其与一个二进制遮罩取与，得到 value 的最高 shift 位。这个遮罩应该是：1111 1111 << (8 - 3) = 1110 0000。于是我们得到 1100 0000。

其次，注意到对于异或运算有如下事实：a ^ b ^ b = a。依靠二进制遮罩，我们已经获得了 value 的最高 shift 位。因此，我们也就能得到 shifted 的最高 2 * shift 位。它应该是 1100 0000 >> 3 = 0001 1000。将其与 result 取异或，则能得到 value 的最高 2 * shift 位。于是我们得到 1101 0000。

我们很容易可以发现，最多只需要进行这样的操作两次即可还原原本的值。

我们同样对其他位数的二进制数进行取样，可以很容易发现，操作次数与位数的关系是： \[ times=bits/shift \] 同理，对于左位移异或也是一样的，但是需要注意的是，一般来说左位移异或会给予一个掩码值确保左异或不会越界，所以写出完整的自位移异或逆算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def unshiftRight(x: int, shift: int, mask: int = None, bits: int = 32):
    if mask is None:
        mask = (1 << bits) - 1
    res = x
    for _ in range(bits // shift):
        res = x ^ res >> shift & mask
    return res

def unshiftLeft(x: int, shift: int, mask: int = None, bits: int = 32):
    if mask is None:
        mask = (1 << bits) - 1
    res = x
    for _ in range(bits // shift):
        res = x ^ res << shift & mask
    return res

value = 0b11010010
shift = 3
result = 0b11001000
print(result == value ^ value >> shift, value == unshiftRight(result, shift, bits=8))