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.
/*
As previously posted this answer, https://stackoverflow.com/questions/4648716#42865348
using a Johnson counter Gray code, is very simple:
Number_of_Bit_To_Flip = ++Number_of_Bit_To_Flip % Total_Number_of_Counter_Bits
which is executed on every event occurrence.
Otherwise, using a Binary Reflected Gray Code and a 4 byte base 2 counter n, ...
Method 1 - using a table
*/
static const byte twos[ ] = { // note pattern V V V V V V
0,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,
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, 6,
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,
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, 7,
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,
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, 6,
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,
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, 8,
};
// operation count worst case 3 logic 4 index 1 addition
// for 7/8 of calls 2 3 1
byte bit_change(byte ctr[4]) {
return
(byte[]){
(byte[]){ 16 + twos[ctr[2]] ,
(byte[]){24 + twos[ctr[3]] ,
31 } [ !ctr[3] ] } [ !ctr[2] ] ,
(byte[]){ 0 + twos[ctr[0]] ,
8 + twos[ctr[1]] } [ !ctr[0] ] }
[ctr[0] || ctr[1]];
// -------- NB. orphaned, included for pedagogic purposes --------
return (byte[]){ 0 + twos[ctr[0]] , // this IS totally time constant
8 + twos[ctr[1]] , // NB. 31 + time "constantator"
16 + twos[ctr[2]] , // case ctr[i]==0 for all i
24 + twos[ctr[3]] ,
31 + twos[ctr[0]] } [ !ctr[0]*( 1+
!ctr[1]*( 1+
!ctr[2]*( 1+
!ctr[3] ) ) ) ];
}
/Method 2 - no tables */
byte bin2toN(byte b){
return
(byte []) {(byte []) {(byte []) {7,6} [b < 128 ] ,
(byte []) {5,4} [b < 32 ] } [b < 64 ] ,
(byte []) {(byte []) {3,2} [b < 8 ] ,
(byte []) {1,0} [b < 2 ] } [b < 4 ] } [b < 16 ] ;
}
byte flip_bit(byte n[4]){
return
(byte []){
(byte []){ 16 + bin2toN( n[2] & -n[2] ) ,
(byte []){ 24 + bin2toN( n[3] & -n[3] ),
31 } [ !n[3] ] } [ !n[2] ] ,
(byte []){ 0 + bin2toN( n[0] & -n[0] ) ,
8 + bin2toN( n[1] & -n[1] ) } [ !n[0] ] }
[ n[0] || n[1] ] ;
// - - - - - - - - - - - - ORPHANED, fails on zero - - - - - - - - - - - -
return // included for pedagogic purposes
(byte []) {
(byte []) { bin2toN( n[2] & -n[2] ) + 16 ,
bin2toN( n[3] & -n[3] ) + 24 } [ !n[2] ] ,
(byte []) { bin2toN( n[0] & -n[0] ) + 0 ,
bin2toN( n[1] & -n[1] ) + 8 } [ !n[0] ] } [ n[0] || n[1] ] ;
}
/*
Bit Bunnies and Cargo Cult Coders have no need to read further.
The efficiency of execution of the above code depends on the fact that n[0], n[1], ...
are computed at compile time as fixed addresses which is quite conventional.
Also, using a call-by-need optimizing compiler will expedite the array contents
so only one indexed value needs to be calculated.
This compiler sophistication is likely missing but it is easy to manually assemble
the raw machine code to do it (basically a switch, computed goto, etc. ).
Analysis of the above algorithms, using the orphaned code, shows that every function
call will execute exactly the same instruction sequence, optimized or not.
In both methods, the non-orphaned returns require handling the case when there
is counter roll over on 0, consequently using extra index and logical
(!) operations. This extra happens for 1/2 of 1/2 of 1/2 or 1/8 of the total counts,
and for one count in this 1/8 there is nothing to do but return 31.
The first method requires 2 logical operations (! ||), 1 addition and 3 index
calculations for 7/8 of the total counts. On a single count of zero, 3 logical and
3 index operations are needed and the rest of the other 1/8 need 3 logical, 1 addition
and 4 index operations.
The final code on execution of method 2 (compiled optimally), for 7/8 of the
calculations, uses 7 logical operations (|| & ! < - the last is two's complement),
1 arithmetic (+) and 5 calculated index operations. The other 1/8, but one
instance, need 8 logical, 1 addition and 6 calculated index operations.
Unfortunately, no flash of divine inspiration manifested any cargo code.
This is an abridged tale of how this composition's authorship happened.
How this was done involved a crucial preliminary investigation as documented:
https://stackoverflow.com/a/42846062.
Then code was derived using a succesive refinement process commencing with an assesment
of the algorithms in this post.
Specifically, this answer: https://stackoverflow.com/a/4657711 .
This algorithm's time variant execution from the loop overhead will be
poignently and prominently accentuated by reducing the return calculation
to a single addition and two index operations.
*/
byte bit_change(byte ctr[4]) {
static byte ones[256]; // this sparse RA is precomputed once
for (byte i = 255; --i; ones[i]=0) ;
ones[ 0] = ones[ 1] = 0; ones[ 3] = 1; ones[ 7] = 2;
ones[15] = 3; ones[31] = 4; ones[63] = 5; ones[127] = 6; ones[255] = 7;
// { ie. this very sparse array is completely adequate for original code
// 0,0, ,1, , , ,2, , , , , , , ,3, , , , , , , , , , , , , , , ,4,
// , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,5,
// , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,
// , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,6,
// , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,
// , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,
// , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,
// , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,7, }
// 1/2 of count uses 2 index 2 conditionals 0 increment 1 logic 2 +/- 1 x
// 1/4 3 4 1 1 2 1
// 1/8 4 6 2 1 2 1
// 1/16 5 8 3 1 2 1
// average 14 = 3.5 5 1.5 1 2 1
unsigned char i; for (i = 0; i < 4; i++) { // original code
unsigned char x = counter[i]; // "works" but
if (x) { // still fails on
x ^= x - 1; // count 0 rollover
return 8 * i + ones[x];
} }
// ............................. refinement .............................
byte x; for (byte i = 0; i < 4; i++) //
if (x = counter[i])
return i<<3 + ones[x ^ x - 1];
}
/--------------------------------------------------------------
--------------------------------/
// for (byte i = 255; --i; twos[i] == ones[i ^ i-1] ) ;
// ones[ ] uses only 9 of 1/4K inefficient, twos[ ] uses all 1/4K
static const byte twos[ ] = {
0,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,
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, 6,
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,
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, 7,
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,
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, 6,
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,
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, 8,
};
// fix count 0 rollover failure, make time absolutely constant as per OP
byte f0(byte ctr[4]) {
byte ansr=31;
for (byte i = 0; i < 4; i++)
if (ctr[i]) {
ansr=(byte[]){0,8,16,24}[i] + twos[ctr[i]]; // i<<3 faster?
break;
}
for (; i < 4; i++) if (ctr[i]) ;
return ansr;
}
//..................................................
// loop ops (average): 1.5 ++ 2.5 [] 5 if
// result calculation: 1 + 2 [] significant loop overhead
byte f1(byte counter[4]) {
for (byte i = 0; i < 4; i++)
if (counter[i])
return (byte[]){ 0 + twos[counter[0]],
8 + twos[counter[1]],
16 + twos[counter[2]],
24 + twos[counter[3]] } [i];
return 31;
}
//..................................................
// 5 +/++ 6 [] 10 if
byte f2(byte counter[4]){
byte i, ansr=31;
for (i = 0; i < 4; i++) { // definite loop overhead
if (counter[i]) {
ansr= (byte[]){ 0 + twos[counter[0]],
8 + twos[counter[1]],
16 + twos[counter[2]],
24 + twos[counter[3]] } [i];
break;
} }
for (; i < 4; i++) if (counter[i]); // time "constantator"
return ansr;
}
//..................................................
// 4 + 4 ! 3 x 1 [] 1 computed goto/switch
byte f3(byte counter[4]){ // default: time "constantator"
switch (!counter[0]*( 1 + // counter[0]==0 !!
!counter[1]*( 1 +
!counter[2]*( 1 +
!counter[3] ) ) ) ){
case 0: return 0 + twos[ counter[0] ] ;
case 1: return 8 + twos[ counter[1] ] ;
case 2: return 16 + twos[ counter[2] ] ;
case 3: return 24 + twos[ counter[3] ] ;
default: return 31 + twos[ counter[0] ] ;
} }
/*
There is a comparable chronology for method 2.
This sequence has been radically attenuated and abbreviated to an intermediate example:
Inadvertently, the code posted in https://stackoverflow.com/a/42865348 was
not the exclusively byte sized one as intended. The intended code is in this post.
*/
byte log2toN(byte b){ return ( b & 0xF0 ? 4:0 ) + // 4444....
( b & 0xCC ? 2:0 ) + // 22..22..
( b & 0xAA ? 1:0 ) ; // 1.1.1.1.
}
// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
byte BRGC(byte n){ return n ^ n>>1; }
byte bitNbyte(byte n){ return log2toN( BRGC(n) ^ BRGC(n+1) ); }
byte bit2flip(byte n[4]){
boolean n3=n[3]<255, n2=n[2]<255, n1=n[1]<255, n0=n[0]<255;
return n0*( 0 + bitNbyte( n[0] ) ) + !n0*(
n1*( 8 + bitNbyte( n[1] ) ) + !n1*(
n2*(16 + bitNbyte( n[2] ) ) + !n2*(
n3*(24 + bitNbyte( n[3] ) ) + !n3*( 0 ) ) ) );
}
// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
byte bit_flip(byte n[4]){
//switch( ( !!n[0] << 3 ) | ( !!n[1] << 2 ) | ( !!n[2] << 1 ) | !!n[3] )
switch( 15 ^ ( !n[0] << 3 ) ^ ( !n[1] << 2 ) ^ ( !n[2] << 1 ) ^ !n[3] ) {
case 15: case 14: case 13: case 12:
case 11: case 10: case 9: case 8: return 0 + log2toN( n[0] & -n[0] );
case 7: case 6: case 5: case 4: return 8 + log2toN( n[1] & -n[1] );
case 3: case 2: return 16 + log2toN( n[2] & -n[2] );
case 1: return 24 + log2toN( n[3] & -n[3] );
default: return 31 + log2toN( n[0] & -n[0] );
} }
/*
Rhetorically, the answer to How do I find ... can only be answered explicitly
in the personal sense (see this answer: https://stackoverflow.com/a/42846062) as
it is not possible to speak for other individuals' cognitive abilities.
The content of https://stackoverflow.com/a/42846062 is crucial for background
information and reflects the very personal
pedantic mechanism required for the mental gymnastics to solve this problem.
Undoubtedly, the milieu and plethora of material is daunting but this is exactly
the personal approach taken in garnering sufficient insight, repertoire, anecdotal
precedents, etc. to extrapolate and interpolate an answer to answer specifically,
what program meets the criteria, exactly. Further, it is this very "chase" that
excites and motivates the (perhaps pathological) psyche to invest time and effort
to satiate curiosity with an inquisitive quest.
*/
void setup() { }
void loop() { }
/*
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];
*/
{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://img.manongdao.com/sparkler-677774__340.jpg', '推荐 仙女界的扛把子 的文章《How do I find next bit to change in a Gray code in》','https://www.manongdao.com/article-298082.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}