迭代n-bit Gray codes的方法有很多种.有些比其他的更有效率。但是,我实际上并不需要格雷码,而是想遍历格雷码列表中更改的位索引,而不是实际的格雷码。例如,采用这个 3 位格雷码列表:
000, 001, 011, 010, 110, 111, 101, 100
我想输出 3、2、3、1、3、2、3。这告诉我们需要更改位 3、2、3 等才能获得列表。在这里,我从 1 和左边开始索引。
一种方法是按顺序计算格雷码,并为每一对连续的 (x, y) 计算 (x XOR y) 以确定更改的位,然后取 (x XOR) 的整数对数基数 2 y)。
但是我需要尽可能快的迭代,我的兴趣是 30-40 位格雷码。
有没有一种有效的方法来做到这一点?
最佳答案
如果您从 0 开始对最低有效位进行编号,则要更改以增加二进制反射格雷码的位的位置是递增二进制数中设置的最低位的位置(请参阅维基百科段落的末尾你链接了) - 要得到你提供的编号,从 3/位数中减去。
binary-reflected ("Gray") 000 001 011 010 110 111 101 100
binary 001 010 011 100 101 110 111
pos of least significant 1 0 1 0 2 0 1 0
(count of trailing zeros ctz)
3 - ctz(binary) 3 2 3 1 3 2 3
关于algorithm - 迭代格雷码更改位置的有效方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41207240/