格雷码算法(32 位或更少)
Gray code algorithm (32 bit or less)
我最近遇到了格雷码,我一直在努力思考用于将格雷码转换回二进制(32 位或更少位)的高效算法。
num = num ^ (num >> 16);
num = num ^ (num >> 8);
num = num ^ (num >> 4);
num = num ^ (num >> 2);
num = num ^ (num >> 1);
这就是我所说的代码。下面是我的问题:
- 这和普通代码(右移 1 和 XOR 直到
mask == 0
)有什么区别?
- 为什么专门使用 16、8、4、2、1 而不是任何其他小于 32 位的数字?
如果我们反过来做有什么区别:
num = num ^ (num >> 1);
num = num ^ (num >> 2);
num = num ^ (num >> 4);
num = num ^ (num >> 8);
num = num ^ (num >> 16);
我已经试过了,结果似乎是一样的。
例如,以位为单位(假设为 8)
h g^h f^g e^f d^e c^d b^c a^b
那么如果我们应用 x ^= x >> 1
会发生什么?我们得到这个
h g f^h e^g d^f c^e b^d a^c
这看起来就像我们开始的那样,就好像它是由 x ^ (x >> 2)
而不是 x ^ (x >> 1)
制作的一样,所以同样的想法只需要移位 2:
h g f e d^h c^g b^f a^e
看起来不错,现在很明显为什么 x ^= x >> 4
会完全恢复正常。对于更多位,相同的模式只会持续一段时间。
另一种看待这个问题的方法是暂时反转位,将 "to gray" 变成 x ⊗ 3
,⊗
在 GF(2k 中乘法),奇数乘法在GF(2k)中是可逆的,3的乘法逆元是"all bits set",可以发现如下:
- 从
y=3
开始,临时反转 i=1
- 通过与 3 异或来杀死
y
中的第一位(不是 lsb),设置相反的相应位
- 循环直到
y=1
所以第一步是 y=3, i=1
、y=5, i=3
、y=9, i=7
等,直到您设置 i
中的所有位,我们称之为最终 i
inv
.
然后我们有(x ⊗ 3) ⊗ inv = x ⊗ (3 ⊗ inv) = x ⊗ 1 = x
乘以"all bits set"意味着每一位最终都是它自己和所有低位的异或,你可以用
x ^= x << 1
x ^= x << 2
x ^= x << 4
...
首先,所有位都与其相邻的位进行异或,然后是接下来的两个位(它们已经被异或在一起,所以这只需要一个步骤),然后是接下来的四位等。
再次反转这些位以获得您开始的内容。
但现在是有趣的东西。
为什么顺序不重要?
(是的,事实上你不仅可以颠倒步骤,还可以任意洗牌)
好的,将位取反,回到GF(2k)。另一种写每一行的方法是
x = x ⊗ 3
x = x ⊗ 5
x = x ⊗ 17
...
最终结果当然是 ((x ⊗ 3) ⊗ 5) ⊗ 17 = x ⊗ (3 ⊗ 5 ⊗ 17) = x ⊗ 127
GF(2k) 中的乘法非常好并且可以交换,所以它可以按任何顺序完成。
其他号码呢
当然可以,只要他们的产品是 inv
。但是所有其他选择都会导致出现 annoying/many 个被乘数。例如,也许我们希望 9 是一个因子,那么剩下的就是 199,它可以分解为 9 ⊗ 63,等等,但是这会持续一段时间,直到你可能有 3、5、9、9、17, 65 这太糟糕了(请注意 9 ⊗ 9 ⊗ 65 = 1 反正如果有 8 位那么是的,只需将其踢出并返回到原始的 3、5、17)。不过可能。
我最近遇到了格雷码,我一直在努力思考用于将格雷码转换回二进制(32 位或更少位)的高效算法。
num = num ^ (num >> 16);
num = num ^ (num >> 8);
num = num ^ (num >> 4);
num = num ^ (num >> 2);
num = num ^ (num >> 1);
这就是我所说的代码。下面是我的问题:
- 这和普通代码(右移 1 和 XOR 直到
mask == 0
)有什么区别? - 为什么专门使用 16、8、4、2、1 而不是任何其他小于 32 位的数字?
如果我们反过来做有什么区别:
num = num ^ (num >> 1); num = num ^ (num >> 2); num = num ^ (num >> 4); num = num ^ (num >> 8); num = num ^ (num >> 16);
我已经试过了,结果似乎是一样的。
例如,以位为单位(假设为 8)
h g^h f^g e^f d^e c^d b^c a^b
那么如果我们应用 x ^= x >> 1
会发生什么?我们得到这个
h g f^h e^g d^f c^e b^d a^c
这看起来就像我们开始的那样,就好像它是由 x ^ (x >> 2)
而不是 x ^ (x >> 1)
制作的一样,所以同样的想法只需要移位 2:
h g f e d^h c^g b^f a^e
看起来不错,现在很明显为什么 x ^= x >> 4
会完全恢复正常。对于更多位,相同的模式只会持续一段时间。
另一种看待这个问题的方法是暂时反转位,将 "to gray" 变成 x ⊗ 3
,⊗
在 GF(2k 中乘法),奇数乘法在GF(2k)中是可逆的,3的乘法逆元是"all bits set",可以发现如下:
- 从
y=3
开始,临时反转i=1
- 通过与 3 异或来杀死
y
中的第一位(不是 lsb),设置相反的相应位 - 循环直到
y=1
所以第一步是 y=3, i=1
、y=5, i=3
、y=9, i=7
等,直到您设置 i
中的所有位,我们称之为最终 i
inv
.
然后我们有(x ⊗ 3) ⊗ inv = x ⊗ (3 ⊗ inv) = x ⊗ 1 = x
乘以"all bits set"意味着每一位最终都是它自己和所有低位的异或,你可以用
x ^= x << 1
x ^= x << 2
x ^= x << 4
...
首先,所有位都与其相邻的位进行异或,然后是接下来的两个位(它们已经被异或在一起,所以这只需要一个步骤),然后是接下来的四位等。
再次反转这些位以获得您开始的内容。
但现在是有趣的东西。
为什么顺序不重要?
(是的,事实上你不仅可以颠倒步骤,还可以任意洗牌)
好的,将位取反,回到GF(2k)。另一种写每一行的方法是
x = x ⊗ 3
x = x ⊗ 5
x = x ⊗ 17
...
最终结果当然是 ((x ⊗ 3) ⊗ 5) ⊗ 17 = x ⊗ (3 ⊗ 5 ⊗ 17) = x ⊗ 127
GF(2k) 中的乘法非常好并且可以交换,所以它可以按任何顺序完成。
其他号码呢
当然可以,只要他们的产品是 inv
。但是所有其他选择都会导致出现 annoying/many 个被乘数。例如,也许我们希望 9 是一个因子,那么剩下的就是 199,它可以分解为 9 ⊗ 63,等等,但是这会持续一段时间,直到你可能有 3、5、9、9、17, 65 这太糟糕了(请注意 9 ⊗ 9 ⊗ 65 = 1 反正如果有 8 位那么是的,只需将其踢出并返回到原始的 3、5、17)。不过可能。