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

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

/*
Can not edit previous answer, as per commentary, so posting rewrite:

Too impatient?
For immediate gratification and minimal edification, cut to the chase and chase this link where only the final result has been posted:
C code for generating next bit to flip in a gray code

REFs:
C code for generating next bit to flip in a gray code
How do I find next bit to change in a Gray code in constant time?

Deriving nth Gray code from the (n-1)th Gray Code
Gray code increment function
Efficient way to iterate over Gray code change positions
Generating gray codes.

https://en.wikipedia.org/wiki/The_C_Programming_Language  
https://en.wikipedia.org/wiki/The_Elements_of_Programming_Style  

WARNING:
For purposes of coding expediency and demonstrable functional execution, some non-trivial programming techniques have been used. However, this is hopefully mitigated for the exposition of the concept rudiments by presenting the essence as trivially and minimally as possible with highlighting by / / / /. Careful reading, study and experiment are encouraged to avoid cargo cult coding, oversights, and perpetrating mistakes.

This answer is manifested in the Arduino IDE ESP8266 core coding environment.

The algorithm as posited by the OP is not exactly correct (as if this;).

The Johnson Code
-------------------------

Since the actual Gray coding is irrelevant, using a Johnson counter's Gray code is an exceptionally easy and poignant way to cognitively and computationally count both the bit to change and the next code.

Note that the Johnson counter Gray code density is linear and not logarithmic.
With 32 bits in 4 bytes, the sequence can count from 0 to 63 before resetting.

It is necessary to verify carefully the functional suitability of the code that follows, modifying it as appropriate.

HINT: Verification is a MUST, especially for the "binary reflected" Gray code (BRGC)!

/./ / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /./

byte  bitCtr=-1;                //   for 4 x 8 bits use 32 instead of 5
byte JohnsonCode(){ static byte GCbits = 0; 
                        return  GCbits ^=  1u << ( bitCtr = ++bitCtr %5 ); }

/./ / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /./

void testJohnson(){           
   Serial.println("\n\tJohnson counter\t   Bit\n\t   Gray code:\t Flipped:");

   for( int intifiny=31; --intifiny;  )
      Serial.println( "\t     " + cut( 5, "....." +  

// s.replace(...) returns zip, 
//                    so VVV use lambda function      invoke via VVV      
//  _____________________ V ____________________   ______________ V _____________ 
   [](String  s){ s.replace("0","."); return s; } ( String( JohnsonCode(), BIN ) )

         ) + "\t    " + bitCtr
      );
}  

/*
Outputs:

  Johnson counter   Bit
     Gray code:   Flipped:
       ....1         0
       ...11         1
       ..111         2
       .1111         3
       11111         4
       1111.         0
       111..         1
       11...         2
       1....         3
       .....         4
       ....1         0
       ...11         1   etc.   

Some background material on the Binary Reflected Gray Code (BRGC)
-----------------------------------------------------------------------------------------------
CONVERSIONS:
---------------------
REF: Code Golf: Gray Code

// These javascript scURIples may run by copy and paste to the URI browser bar.

// convert base 2  to  BRGC:   n^=n>>1  
//     get base 2 from BRGC:   n^=n>>1   n^=n>>2   n^=n>>4  ...

javascript:      n=16; s="<pre>";  
                      function f(i,n){ return i?f(i>>1,n^n>>i):n}
                                  while(n--) s +=  f(4,n^n>>1) .toString(2)+"\n";

javascript:      n=16; s="<pre>"; while(n--) s +=     (n^n>>1) .toString(2)+"\n";

javascript: c=0; n=16; s="<pre>"; while(n--) s +=(c^(c=n^n>>1)).toString(2)+"\n";

COUNTING:
-----------------
The following (as per ref. above) arbitrarily gets both the preceding and following BRGC's for a code.
NB! The order of n1 and n2 is parity determined and non-corresponding otherwise. The ordering might be n1, gray, n2 OR it could be n2, gray, n1, so, eo (parity) discriminates.

unsigned n1 = gray ^ 1;
unsigned n2 = gray ^ ((gray & -gray) << 1); 
gray = eo=!eo ? n1 : n2;                   // eo (or parity) gets Every Other  

ie.

bitToFlip =  eo=!eo ? 1 : (gray & -gray) << 1;   gray ^= bitToFlip;  

hence

    gray ^=  eo=!eo ? 1 : (gray & -gray) << 1;    

/./ / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /./

byte tooGray( byte (*f)(byte) ){ 
   static byte BRGC=0, base2=0;
   static boolean eo=false;              
   return  

       (*f)(  BRGC ^= (eo=!eo) ? (BRGC & -BRGC) <<1 : 1 )  & 0x3 |
   //  count  ^---------------------------------------^  in raw BRGC   


       (*f)(           base2   ^   base2++ >>1          )  & 0xC ; }
   //  count in base 2 ^---------------------^ and convert to BRGC

/./ / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /.

REF: The neighbors in Gray code

http://www.graphics.stanford.edu/~seander/bithacks.html   
http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html  
https://en.wikipedia.org/wiki/Ring_counter#Johnson_counter   

Oh yeah, ... count set bits in A ^ A+1 which will have a bit pattern like 000...0111..1 Prove.

How to get bit position for a power of 2 - the n parameters must have a single bit set.

Method 1
*/

byte naive1(byte n){ return  bitNumber(n-1);   }  

byte bitNumber(byte m){  // can use A ^ A+1  ...  BUT >> 1 first OR -1 after
 return ( m & 1  ?1:0 ) + ( m &  2 ?1:0 ) + ( m &  4 ?1:0 ) + ( m &   8 ?1:0 ) +
        ( m & 16 ?1:0 ) + ( m & 32 ?1:0 ) + ( m & 64 ?1:0 ) + ( m & 128 ?1:0 );}
       //    256               512              1024               2048  ...

/*
Method 2
*/

byte naively2(byte n){
 return ( n & 1  ?0:0 ) + ( n &  2 ?1:0 ) + ( n &  4 ?2:0 ) + ( n &   8 ?3:0 ) +
        ( n & 16 ?4:0 ) + ( n & 32 ?5:0 ) + ( n & 64 ?6:0 ) + ( n & 128 ?7:0 );}

/*
Method 3
*/

byte powerOf2(byte n){ return ( n & 0xF0 ? 4:0 )  +   //    4444....
                              ( n & 0xCC ? 2:0 )  +   //    22..22..
                              ( n & 0xAA ? 1:0 )  ; } //    1.1.1.1.

/*
Method 4
*/

// and the penultimate,
//    http://www.graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn

byte fastNof2up(byte b){ return (byte []){0,1,6,2,7,5,4,3}[(byte)(b*0x1Du)>>5];}
//                                        7,0,5,1,6,4,3,2           0x3Au
//              b==2^N                    0,1,2,4,7,3,6,5           0x17u
//                                        7,0,1,3,6,2,5,4           0x2Eu
//     |------|                 |------|        
//     .....00011101         ........1101....     
//    ......0011101.        .........101.....     
//   .......011101..       ..........01......   
//  ........11101...      ...........1.......       
//     |------|                 |------|

/*
Method 5
Details are at the end.
Can a judicious choice of constants reduce this to only 2 operations?
*/

byte log2toN(byte b){ return 7 - (byte) ( 0x10310200A0018380uLL >> ( (byte)(0x1D*b) >>2 ) ) ; }  

/*
Testing Environment
*/

void setup() {Serial.begin(115200);  testJohnson();  test(); fastLog2upN(0);  }

void loop() {   delay(250);  // return ;
  [](byte GrayX2){  Serial.print( GrayX2 ^ 0x0F ? "" : baq(GrayX2)+"\n"); 
   analogWrite( D5, (int []) { 0, 1200,    0, 300 }  [ GrayX2      & 0x3 ] );
   analogWrite( D6, (int []) { 0,    0, 1200, 300 }  [ GrayX2      & 0x3 ] );
   analogWrite( D7, (int []) { 0, 1200,    0, 300 }  [ GrayX2 >> 2 & 0x3 ] );
   analogWrite( D8, (int []) { 0,    0, 1200, 300 }  [ GrayX2 >> 2 & 0x3 ] ); } 
//                                    (  tooGray(           b              )  );
                                      (  tooGray( [](byte n) { return n; } )  );
}

/======================================================================
Caveat:
-----------
The OP's algorithm is not effective.

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

as seen when coded as:
*/

void test(){
 static byte C=0, bits=0; 
 Serial.println((String)"\n  "+(3^2+1)+"  "+(3^(2+1))+"  "+((3^2)+1) );
 Serial.println(
  "\n                                         manifested by an        actual               "
  "\n                                        obstinate perverse       bit to               " 
  "\n                                              psyche              flip           check" 
  "\n      A            A+1         A ^ A+1       B^=A^A+1         (A^A+1)+1>>1            ");
 for(int intifiny=32, A=0; intifiny--; A=++A%15)  // sort a go infinite ... an epiphany!
  Serial.println( (String) pad(  b(  bits ^=  b( b(A) ^ b(A+1) )  )   ) +"    "+ 
                    baq( (A^A+1)+1>>1 ) +"    "+ baq( C^=(A^A+1)+1>>1 )  +"    "
                                              //       "| "+   pad(A)+" "+ pad(bits)
                    );
  Serial.println(
   "                                      |                                    "
   "\n                                     BITS:                                 " 
   "\n                              Bit Isn't This Silly                         " 
   "\n                               Bit Is Totally Set    (A ^ A+1) & -(A ^ A+1) == 1 ALWAYS " 
 "\n\n non-binary Gray codes?                                                    "
   "\n  {-1,0,1} balanced ternary, factoroid (factoradic), {0,-1} negated binary \n");
}  //  https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm  

//   some service routines  ...

String cut(byte sz, String str) { return     str.substring(str.length()-sz)   ; }
String pad(byte n             ) { return cut( 4, "         " + String(n,DEC) ); }
String baq(byte n             ) { return cut( 9, "........." + String(n,BIN) ); }
void   q  (                   ) {          /*  PDQ QED PQ's */         } 
void   p  (         String str) { Serial.print( "  " + str + "   " ) ; }
byte   d  (byte n             ) {  p(pad(n));         return n       ; }   
byte   b  (byte n             ) {  p(baq(n));         return n       ; }  

/*
Sample output:

                                                                flip  bit                      
                                                               "correctly"    confirm?           
      A            A+1         A ^ A+1       B^=A^A+1         (A^A+1)+1>>1                 
  ........0     ........1     ........1     ........1      1    ........1    ........1   |    0    1
  ........1     .......10     .......11     .......10      2    .......10    .......11   |    1    2
  .......10     .......11     ........1     .......11      3    ........1    .......10   |    2    3
  .......11     ......100     ......111     ......100      4    ......100    ......110   |    3    4
  ......100     ......101     ........1     ......101      5    ........1    ......111   |    4    5
  ......101     ......110     .......11     ......110      6    .......10    ......101   |    5    6
  ......110     ......111     ........1     ......111      7    ........1    ......100   |    6    7
  ......111     .....1000     .....1111     .....1000      8    .....1000    .....1100   |    7    8
  .....1000     .....1001     ........1     .....1001      9    ........1    .....1101   |    8    9
  .....1001     .....1010     .......11     .....1010     10    .......10    .....1111   |    9   10
  .....1010     .....1011     ........1     .....1011     11    ........1    .....1110   |   10   11
     etc.                             |                                    
                                     BITS:                
                              Bit Isn't This Silly             Houston; We have a (an-other) problem    
                               Bit Is Totally Set                    
                        (A ^ A+1) & -(A ^ A+1) == 1 ALWAYS           

Curious?
-----------
The following code is a very very crude method that can expedite a hunt for suitable bit packed counting candidates to compute log 2^n (in base 2 ie. n).
*/

byte fastLog2upN(byte b){                            //  b==2^N
    for(long long int i=8, b=1; --i;    )
        Serial.println((int)(0x0706050403020100uLL / (b*=0x100)),HEX)  ; 
    for( int i=9, b=1; --i;b*=2)        //   3A = 1D*2
        Serial.println( 
          (String)      (                           (b>>4 | b>>2 | b>>1) & 7   )   +   "    \t" + 
                        (                                   (0xB8*b) >>8 & 7   )   +   "    \t" + 
                        (                                   (0xB8*b) >>7 & 7   )   +   "    \t" + 
                        (                                   (0x1D*b) >>4 & 7   )   +   "    \t" + 
                        (                                   (0x0D*b) >>3 & 7   )   +   "   |\t" + 
                        (                            ((byte)(0x9E*b) >>2       ) ) +   "    \t" + 
                 (byte) ( 0x07070301C0038007uLL >>   ((byte)(0x9E*b) >>2       ) ) +   "    \t" + 
                        (                            ((byte)(0x1E*b) >>2       ) ) +   "    \t" + 
                 (byte) (  0x7070001C0038307uLL >>   ((byte)(0x1E*b) >>2       ) ) +   "    \t" + 
                        (                            ((byte)(0x5E*b) >>2       ) ) +   "    \t" + 
                 (byte) (  0x703800183838307uLL >>   ((byte)(0x5E*b) >>2       ) ) +   "  \t| " + 
                        (                            ((byte)(0x3A*b))>>5       )   +   "    \t" + 
                        (                            ((byte)(0x3A*b))>>4       )   +   "    \t" + 
                        (                            ((byte)(0x3A*b))>>3       )   +   "    \t" + 
                        (                            ((byte)(0x3A*b))>>2       )   +   "    \t" + 
                        (                            ((byte)(0x3A*b))>>1       )   +   "    \t" + 
                        (                            ((byte)(0x3A*b))>>0       )   +   "  \t| " + 
                 (byte) ( 0x0203040601050007uLL >> 8*((byte)(0x3A*b) >>5       ) ) +   "    \t" + 
          String((byte) ( 0x0706050403020100uLL >>   ((byte)(0x3A*b) >>4       ) ),HEX ) + "\t" + 
          String((byte) (       0x0020010307uLL >>   ((byte)(0x3A*b) >>3       ) ),HEX ) + "\t" + 
          String((byte) ( 0x10300200A0018007uLL >>   ((byte)(0x3A*b) >>2       ) ),HEX ) + "\t|" + 
                        (                            ((byte)(0x1D*b))>>2       )   +   "    \t" + 
                 (byte) ( 0x10710700E0018380uLL >>   ((byte)(0x1D*b) >>2       ) ) +   "    \t" + 
                 (byte) ( 0x10310200A0018380uLL >>   ((byte)(0x1D*b) >>2       ) ) +   "  \t| " + 
       "") ;
   } 

/*

javascript: x=6; y=4; n=511; ra=[]; s="<pre>x"; 
   while(n--)for(i=5;i;i=i==3?2:--i){ 
      j=0; 
      for(b=1;b<129;b*=2) ra[j++]=((n*b)&0xFF)>>i;
      ra.sort(function(a, b){return a-b});
      if ( tf=ra[--j] < 64 &&  ra[1]>ra[0]+x ) 
         while( --j && ( tf = (ra[j]>ra[j-1]+x) || ( ra[j]<ra[j-1]+y  && ra[j+1]>ra[j]+x) ) );
      if(tf) s+="\n "+n.toString(16)+" >> "+i+" \t"+ra.join("  "); 
   }; 
  s;

// many >>2 's   to do: sledge hammer creation of acceptable bit pattern solutions
// only want btf's - Bits That Fit (in 8 bytes): (tf=ra[j-1] < 64)
// program proximity control so no BS (Brain Strain!): tf = (ra[j]<ra[j-1]+x) || (ra[j]<ra[j-2]+y) 
// for debug: s+="\n "+n.toString(16)+" >> "+i; 
// for debug: s+="\n" +tf+"\t"+ra[j]+"\t"+ra[j-1]+"\t"+ra[j-2];  

*/