高效迭代灰码变化位置的方法

Question

有许多方法可以迭代 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位格雷码上。

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

- Simd

---

我有点好奇为什么代码生成本身需要非常高效。据我理解，枚举和生成变更位置列表的算法复杂度（以大O符号表示）并不比枚举本身的生成更大。为什么性能至关重要？ - Codor

@Codor 我正在使用它来加速计算永久性（https://en.wikipedia.org/wiki/Computing_the_permanent）。恒定因素的加速将对我产生很大影响。 - Simd

Answer 1

如果你从最低有效位开始给位数编号，那么为了增加二进制反射格雷码，需要更改的位的位置是一个递增的二进制数中最低位设置的位置（请参见您链接的维基百科段落末尾）- 要获得您呈现的编号，请从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

- greybeard

---

我正在努力理解这个。您是否从0到2 ^ n-1按顺序迭代，并仅查看设置了最低位的位置的每个值？因此，您根本不会计算Gray代码吗？如果真是这样，那似乎非常简单。 - Simd

你确实是按顺序从0到2^n-1逐步迭代吗？是的。那么你实际上从未计算过格雷码吗？不是的。如果是真的，这似乎非常简单。你重新阅读了维基百科上的“构造_n_位格雷码”文章了吗？特别是最后两句话，你试图理解它们吗？ - greybeard

我一定是误解了，但它似乎说“在步骤i>0中，在i的二进制表示中找到最低有效位的位位置，并翻转前一个代码中该位置上的位”。此外，在您的示例中，您按顺序从001迭代到111以获得“二进制”行。最后一行似乎只是查看第二行中尾随零的数量。您在示例中根本没有使用“二进制反射”行，对吗？ - Simd

最后一行似乎只是从第二行中查找尾随零的数量 - 几乎是这样：它是#位数 - #尾随零。我插入了#尾随零=最低有效位1的位置，并改进了行标签。 - greybeard

Answer 2

如果你使用的是例如C语言和GCC内置函数库（而且你肯定应该使用一种可以对汇编输出进行精细控制以便你可以向量化的语言），那么你可以这样做：

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

通过计算计数器ctr的尾随零，此代码将返回0、1、0、2、0、1、0、3、0、1等。根据需要进行翻译。

- David Eisenstat

---

看起来 __builtin_ctzll 函数返回前导零的数量。我们是否还需要计算格雷码并在相邻的格雷码之间执行异或运算，就像问题中那样？我不理解仅计算前导零如何足够。 - Simd

看起来 __builtin_ctzll 返回前导零的数量（从最低有效位开始，clz 是前导）：GCC 文档。 - greybeard

哦，我明白了...你的答案和greybeard的一致。 - Simd