How do I find next bit to change in a Gray code in constant time?

Question

I have a small 8-bit processor which has a N-to-M decoder on some output lines - eg, for the 5 to 32 bit case, I write 00101 and bit 5 changes state. The only interface to the output is change-state, there is no read-back.

The device counts rapidly (but randomly) occuring events, and should provide this count as a 'single bit changes' code to another device. The output pins are read in parallel by another device, and may be read as rapidly or as sparingly as the other device decides, so the count is necessary.

I do NOT need to use the standard Binary Reflective Gray code - I can use any single-bit changing code.

However, I want to be able to track the next bit to change efficiently.

I do not have a "LowestBitSet" instruction, and finding lowest bit set across four 8 bit registers is cycle consuming - so I cannot use this "common" approach:

  Keep binary counter A
  Find B as A XOR (A+1)
  Bit to change is LowestBitSet in B 

I wish to calculate this in as little memory and registers as possible, and memory is definitely too restricted for any large lookup table. Cycle time is the more important factor.

Any suggestions on algorithms?

Answer 1

"Algorithm L" on page 10 of Knuth, Donald E. "Generating all n-tuples." The Art of Computer Programming, Volume 4A: Enumeration and Backtracking, pre-fascicle 2a, October 15, 2004 seems ideal. Step L4 would be "change_state(j)" for your device.

Answer 2

You don't need to calculate the Gray codes and xor them, you can just use the counter itself, and then use a 256-element lookup table to count the number of trailing zeros. Like this:

unsigned char bit_change(unsigned char counter[4]) {
  static const unsigned char ones[] = {
    0,0,0,1,0,1,1,2,0,1,1,2,1,2,2,3,0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
    0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
    0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
    0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
    2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,    
  };

  unsigned char i;
  for (i = 0; i < 4; i++) {
    unsigned char x = counter[i];
    if (x) {
      x ^= x - 1;
      return 8 * i + ones[x];
    }
  }
}

If you unroll the loop, this is at most 2 adds, 1 xors, and 5 loads (but almost always less). If you don't have 256 bytes for the table, you could use the same strategy on nibbles.

Answer 3

LowestBitSet(A ^ (A+1)) is always 0, unless you work for IBM. I think you mean HighestBitSet(), which is roughly the same as log_2().

The bit-twiddling hack immediately preceeding the one linked by AShelly will be much more feasible on an 8-bit micro.

This should make your original algorithm fairly practical, generating { 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, ... }.

As for the possibility of changing to a different sequence which would also generate a Gray code, for the purpose of making it easier to compute, that's very interesting but I haven't come up with anything.