Efficient way to iterate over Gray code change positions

Question

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?

Niobous

I'm a bit curious why the code generation itself needs to be critically efficient. To my understanding, the algorithmit complexity (in terms of Big-Oh-notation) of enumeration and generation of the change position list is not larger than the generation of the enumeration itself. Why exactly is performance critical? – Intervale

@Intervale I am using it to speed up the computation of the permanent (en.wikipedia.org/wiki/Computing_the_permanent ) . Constant factor speedups will make a big difference to me. – Niobous

Answer 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

Literally

I am trying to understand this. Do you literally iterate in order from 0 to 2^n-1 and for each value just look at the position of the lowest bit set? So you never actually compute the Gray codes at all? That seems very simple if true. – Niobous

Do you literally iterate in order from 0 to 2^n-1 in steps of 1, yes. So you never actually compute the Gray codes at all? no. That seems very simple if true. Did you revisit wikipedia on Constructing an n-bit Gray code, trying to understand the last two sentences of that paragraph, in particular? – Literally

I must be misunderstanding it but it does seem to say "at step i>0 find the bit position of the least significant 1 in the binary representation of i and flip the bit at that position in the previous code". Also in your example you iterate from 001 up to 111 in order in the "binary" line. The last line seems to just look the number of trailing zeros from line two. You don't use the "binary-reflected" line at all in your example do you? – Niobous

The last line seems to just look the number of trailing zeros from line two - almost: it is #bits - #trailing zeros. I inserted the #trailing zeros = position of least significant 1 and improved the line label. – Literally

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

Armistead

It looks like __builtin_ctzll returns the number of leading zeros. Do we also need to compute the gray code and do the XOR operation between successive Gray codes as in the question? I don't understand how just counting the number leading zeros can be enough. – Niobous

looks like __builtin_ctzll returns the number of leading zeros trailing (from least significant, clz is leading): GCC docs. – Literally

Oh I see... your answer goes together with greybeard's. – Niobous