Efficient way to iterate over Gray code change pos

问题:

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

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.

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).

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?

回答1:

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

回答2:

If you're working with, e.g., C with GCC intrinsics (and you definitely should be using a language that gives you fine control over the assembly output so that you can vectorize), then you can do

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

This returns 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, ... by counting the trailing zeroes of the counter ctr.

Translate as appropriate.