3

有多种迭代n 位格雷码的方法。有些比其他的更有效率。但是，我实际上并不需要格雷码，而是希望遍历格雷码列表中更改的位索引，而不是实际的格雷码。例如，以这个 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 y) 的整数对数基数 2。

但是我需要尽可能快的迭代，我的兴趣将是 30-40 位格雷码。

有没有一种有效的方法来做到这一点？

4

2 回答 2

3

如果您从 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
于 2016-12-18T13:05:55.020 回答
2

如果您正在使用例如带有 GCC 内在函数的 C（并且您绝对应该使用一种可以让您对汇编输出进行精细控制以便可以矢量化的语言），那么您可以这样做

long long ctr = 0LL;
int next() { return __builtin_ctzll(++ctr); }

这通过计算 counter 的尾随零返回 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, ctr...

酌情翻译。

于 2016-12-19T01:49:54.250 回答