# How to create a graycode of N bits with a code-agnostic iteration function

I'm posting this as more of a theory/mathematic how-to followup to a stackoverflow question.

The non-iterative method for calculating graycode depends on Log2N bytes, to store position information for the next bit in the iteration sequence.
Specifically, the goal is to know the next bit to change without having to look at the current code.

However, for the 3 bit gray code, there's a iteration sequence 0,1,2,1,0,1,2,1 that can be represented with a much simpler function - maintain "0,1,2,1" in a register and rotate each time (as an example of a more general permutation).
To reduce the necessary state, this could be kept in two positions, starting 0,1 and a constant function of "xor, permute" applied: 0,3 => 1,0 => 2,1 => 3,2 => 0,3 (the bit to change being the first, and 3 handled as 1 since only 0,1,2 are valid)

Is it possible for graycodes to exist for higher values of N, such that the iteration function can be calculated with just a permutation operation?
If not, with permute/xor?
Is there a more general way to think of applying constant operations to define the state change?

-
You should define what a Gray code is, at least. –  Glen Wheeler Jan 13 '11 at 15:48
@Glen Wheeler, a Gray code of length 2^n has the property that neighbours differ in exactly one bit. –  TonyK Jan 13 '11 at 16:00
@frLich:The standard 3-bit Gray code is 0 1 3 2 6 7 5 4. How is this generated by your iteration sequence? I confess your question leaves me baffled. –  TonyK Jan 13 '11 at 16:01
@TonyK: I assume he is talking about $(n,k)$-Gray codes. –  Brandon Carter Jan 13 '11 at 16:05
tony, that's the binary reflected gray code sequence - but this iteration sequence also produces a valid arrangement of the numbers -0,1,3,7,5,4,6,2 –  frLich Jan 13 '11 at 16:11

The iteration function at stage $t$ is the highest power of $2$ that divides $t$ (this will result in a somewhat different code than yours, but still goes over all numbers, changing only one bit at a time). In general, since there are $n$ possible bits to flip, you will have to store at least $\log_2 n$ bits in memory (if you're not allowed to look at the actual counter).

Some processors have a machine instruction that calculates this "highest power of $2$ dividing a number", or perhaps something similar like "leading zero". This is an efficient way to implement Gray counting.

If you don't have such a machine instruction, another good choice is to unroll the increment loop for some small $2^K$, and use some smart iterative approach (using lookup tables) to handle the updates which are not hard-coded.

-
highest power of 2 dividing a number stackoverflow.com/questions/2679815/previous-power-of-2 –  uncle brad Jan 13 '11 at 18:37
Your answer points to the confounding flood on Google. From the link, "calculating highest power of $2$" requires iteration on a mirror of the counter - whereas with this specific sequence, the answer is known in constant time without needing the counter. Thus the question of how to find similar sequences for larger N instead of using binary reflected gray code. –  frLich Jan 14 '11 at 1:43

Set $a_0=0$. To get $a_{n+1}$ from $a_n$, just change bit $r_n$, where $r_n$ is the number of trailing $1$-bits in the binary representation of $n$. So we get:

$(r_n) = \lbrace 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,\dots \rbrace$

$(a_n) = \lbrace 0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8,24,25,27,26,30,31,29,28,20,\dots \rbrace$

This construction gives the standard Gray code.

-
TonyK - Thanks for this answer - Without keeping track of An, what is the minimal amount of state to keep to go from Ri to Ri+1 ? –  frLich Jan 16 '11 at 2:18
You can calculate $r_i$ on the fly, just by counting the trailing $1$-bits in $i$. –  TonyK Jan 16 '11 at 11:37
Reading your comment again, it looks like you might have confused $a_n$ with $r_n$. Here, $a_n$ is the number you want: the $n$th Gray code. You can compute $a_{n+1}$ from just $a_n$ and $n$ (because you can easily get $r_n$ from $n$). –  TonyK Jan 16 '11 at 11:40
I'm looking for a sequence of R, such that I don't need to iterate on Rn to get Rn+1 (counting trailing 1 bits would be iteration). With the 3 bit example, going from Rn to Rn+1 just takes shufling. I don't want to hold the An anywhere if possible. –  frLich Jan 16 '11 at 17:11
Well then, I really don't know how to satisfy you. –  TonyK Jan 17 '11 at 10:32