迭代格雷码更改位置的有效方法 [英] Efficient way to iterate over Gray code change positions

问题描述

有多种方法可以迭代 n位格雷码.有些比其他的更有效率.但是，我实际上不需要格雷码，而是想遍历格雷码列表中更改的位索引，而不是实际的格雷码.例如，请使用以下3位格雷码列表:

There a number of ways iterating over n-bit Gray codes. Some are more efficient than others. However, I don't actually need the Gray codes and would like instead to iterate over the bit index that is changed in a Gray code list, not the actual Gray codes. For example, take this 3-bit Gray code list:

000，001，011，010，110，111，101，100

000, 001, 011, 010, 110, 111, 101, 100

我想输出3、2、3、1、3、2、3.这告诉我们我们需要更改位3、2、3等以获取列表.在这里，我从1开始，从左开始索引.

I would like to output 3, 2, 3, 1, 3, 2, 3. This tells us we needed to change bits 3, 2, 3 etc. in order to get the list. Here I am indexing from 1 and from the left.

执行此操作的一种方法是依次计算格雷码，并为每个连续对(x，y)计算(x XOR y)以标识更改的位，然后采用(x XOR的整数对数2 y).

One way to do this would be to compute the Gray codes in order and for each consecutive pair (x, y) compute (x XOR y) to identify which bit changed and then take the integer log base 2 of (x XOR y).

但是我需要尽可能快地进行迭代，而我的兴趣是使用30-40位格雷码.

However I need the iteration to be as fast as possible and my interest will be in 30-40 bit Gray codes.

是否有一种有效的方法来做到这一点?

Is there an efficient way to do this?

推荐答案

如果您将以0开头的位编号为最低有效位，则更改位置以增加二进制反射的格雷码的位置将是最低位位以递增的二进制数设置(请参见链接的Wikipedia段落的末尾)-要获得显示的编号，请从3/位数中减去.

If you number the bits starting with 0 for least significant, the position of the bit to change to increase a binary-reflected Gray code is the position of the lowest bit set in an increasing binary number (see end of the wikipedia paragraph you linked) - to get the numbering you presented, subtract from 3/the number of bit positions.

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

这篇关于迭代格雷码更改位置的有效方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！