我有一个小型 8 位处理器，它在一些输出线上有一个 N 到 M 解码器 - 例如，对于 5 到 32 位的情况，我写 00101 并且位 5 更改状态。输出的唯一接口是更改状态，没有回读。
设备对发生的事件进行快速（但随机）计数，并应将此计数作为“单个位更改”代码提供给另一个设备。输出引脚由另一个设备并行读取，并且可以根据其他设备的决定尽可能快地或尽可能少地读取，因此计数是必要的。
我不需要使用标准的二进制反射格雷码 - 我可以使用任何一位更改代码。
但是，我希望能够跟踪下一点以有效地进行更改。
我没有“LowestBitSet”指令，并且在四个 8 位寄存器中找到最低位设置是耗时的 - 所以我不能使用这种“通用”方法：
Keep binary counter A
Find B as A XOR (A+1)
Bit to change is LowestBitSet in B
我希望在尽可能少的内存和寄存器中计算它，而且对于任何大型查找表来说，内存肯定太有限了。周期时间是更重要的因素。
对算法有什么建议吗？
LowestBitSet(A ^ (A+1))始终为 0，除非您为 IBM 工作。我想你的意思是HighestBitSet()，大致相同log_2()。
紧接在 AShelly 链接的那个之前的位旋转黑客在 8 位微控制器上将更加可行。
这应该使您的原始算法相当实用，生成{ 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, ... }.
至于为了更容易计算而更改为不同的序列也会生成格雷码的可能性，这很有趣，但我没有想出任何东西。
“算法 L”在Knuth 的第 10 页，Donald E.“生成所有 n 元组”。计算机编程的艺术，第 4A 卷：枚举和回溯，前分册 2a，2004 年 10 月 15 日似乎很理想。对于您的设备，步骤 L4 将是“change_state(j)”。
您不需要计算格雷码并对它们进行异或，您可以使用计数器本身，然后使用 256 元素查找表来计算尾随零的数量。像这样：
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];
}
}
}
如果展开循环，则最多为 2 次加法、1 次异或和 5 次加载（但几乎总是更少）。如果表没有 256 个字节，则可以对半字节使用相同的策略。
对于二进制反射格雷码，请参阅此答案以获取计算代码 N 的有效方法。
与先前的代码进行异或以获得仅设置要更改的位的值。
然后，您可以使用这个 Bit Twiddling Hack（“v 是 2 的幂”的情况）找到只有 3 个操作和 32 个条目的表的位索引。
伪代码是这样的：
n = lastCode = 0
increment:
n+=1
newCode = GrayCode(n)
delta = newCode XOR oldCode
bitToToggle = BitIndex(delta)
old code = new code
GOTO increment;
我一直在尝试理解算法 L，为此，我想我找到了一些我想分享的潜在有用的直觉。
首先要注意要翻转的位的模式是递归和对称的。
0 1 0 2 0 1 0 3 0 1 0 2 0 1 0
现在把它们想象成一棵树是有道理的。
3
2 2
1 1 1 1
0 0 0 0 0 0 0 0
因此由以下算法生成：
def gen(arg):
if arg == 0:
print(arg)
else:
gen(arg - 1)
print(arg)
gen(arg - 1)
上面的树可以解释为该算法的激活帧树。
如果我们打印一个非零数字，下一个数字很明显，它必须是 0。因此，预测下一个元素的问题简化为只预测 0 之后会发生什么。
这是一个有趣的观察，在 0 之后的下一个必须是树中最近的祖先，因此它位于当前位置的右侧。这建议使用以下算法传播右父元素并因此预测下一个元素：
def gen(arg, right_parent):
if arg == 0:
print("%s %s" % (0, right_parent))
else:
gen(arg - 1, arg) # The right parent of my left child is me
print("%s %s" % (arg, 0))
gen(arg - 1, right_parent) # The right parent of my right children is my right parent.
这是一个带注释的树，右父母写在括号中：
3(4)
2(3) 2(4)
1(2) 1(3) 1(2) 1(4)
0(1) 0(2) 0(1) 0(3) 0(1) 0(2) 0(1) 0(4)
这种方法的问题在于，当我们执行它时，代码可能会经历多个调用或返回的步骤，因此连续打印之间花费的时间不是恒定的。我们可以说时间是摊销常数，毕竟，每一对 push 和 pop 都与打印一个数字相关联。
这是另一个想法。当我们打印数字时，我们知道堆栈帧在下一次打印相同的数字之前就消失了，我们是否可以预先加载返回和调用同一帧的工作？
当第一个 0 被打印出来时，我们知道它的右父是 1，所以right_parent当它再次进行递归调用时，它会传递它自己的。
我们在这条规则中总结了这一观察：
right_parent一个帧的值恰好比当前帧大 1，那么right_parent下一次调用的right_parent值将是右父帧的值。打印第二个 0 时，我们知道它的右父是 2，因此下一次调用将通过右父的第二个递归调用的多个步骤完成。任何多步调用都会导致它是一个左孩子，而一个左孩子的右父母总是比当前帧大1！
我们在这条规则中总结了这一观察：
right_parent一帧的值比当前帧的值大 1 以上，那么right_parent下一次调用的值将恰好比当前帧的值大一。有了这两个规则，我想出了这个算法：
def gen():
right_parent = [1,2,3,4]
cur = 0
for i in range(0, 15):
print(cur)
j = right_parent[cur]
if j == cur + 1:
if j != 4: # Avoid index outside of the list
right_parent[cur] = right_parent[j]
else:
right_parent[cur] = cur + 1
if cur == 0:
cur = j
else:
cur = 0
这是 O(1)，但不是算法 L，它不涉及比较。为了探索，这些评论可能会有所启发：
def gen():
right_parent = [1,2,3,4]
cur = 0
for i in range(0, 15):
print(cur)
next = right_parent[cur]
if next == cur + 1:
if next != 4:
right_parent[cur] = right_parent[cur + 1] # f[j] = f[j + 1]
else:
right_parent[cur] = cur + 1 # f[j + 1] = j + 1
if cur == 0:
cur = next # j = f[0]
else:
cur = 0 # f[0] = 0
gen()
感觉就像算法 L 在同一个迭代中以某种方式处理了左和右。这可能与 Knuth 的演讲中的“主动”和“被动”概念有关，但我决定到此为止。我认为对于如何开发算法的直觉来说已经足够了。
OP 提出的算法不会生成任何格雷码。
此答案中的算法：https : //stackoverflow.com/a/4657711/7728918 不是恒定时间，因为条件测试if (x)可以根据counter[i]. 这会改变计算位数所需的时间量。任何单个计算都可能有 4 种不同的可能执行时间。
请参阅（货物崇拜编码员除外）满足此恒定时间要求的以下基本原理的参考（没有灯，没有汽车，没有单一的奢侈品......甚至没有“桌子”）：
byte log2toN(byte b){
return 7 - (byte) ( 0x10310200A0018380uLL >> ( (byte)(0x1D*b) >>2 ) ) ; }
byte BRGC(byte n){ return n ^ n>>1; }
byte bit2flip(byte n){ return log2toN( BRGC(n) ^ BRGC(n+1) ); }
但是，有一种更好、更简洁、更方便的方法来满足 OP 的标准。
对于货物崇拜编码目的，以下方便地满足 OP 的条件最低限度（最大限度？；）。
每次只有两个操作可以找到要更改的位数：模数（如果完成模数2^n可以像位&操作一样简单，n-1即常量2^n - 1）和增量。
实际的约翰逊格雷码 (JGC) 序列是XOR通过将前一个代码与所需位相结合而增量生成的，该位通过左移 1 选择到位号位置。根据 OP 的要求，不需要 此计算。
约翰逊密码
-------------
实际的格雷码无关紧要，因此使用约翰逊计数器的格雷码非常简单。
请注意，约翰逊格雷码 (JGC) 密度是线性的，而不是像基数 2 或二进制反射格雷码 (BRGC) 那样的对数。
使用 4 个字节中的 32 位，序列可以在复位之前从 0 计数到 63。
/ ./ / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /。
byte bitCtr=-1; // for 4 x 8 bits use 32 instead of 5
int JohnsonCode(){ static byte GCbits = 0;
return GCbits ^= 1u << ( bitCtr = ++bitCtr %5 ); }
/ ./ / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /。
测试输出：
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.
部分使用此代码生成：
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
);
}
/*
不幸的是，这个答案没有解释“你（我，我，......）如何找到......”。
有关寻找此类解决方案和类似地使用 BRGC 的方法的详细信息……
请参阅以前的参考文献：https ://stackoverflow.com/a/42846062/7728918
/*
正如之前发布的这个答案，https://stackoverflow.com/questions/4648716#42865348
使用约翰逊计数器格雷码，非常简单：
Number_of_Bit_To_Flip = ++Number_of_Bit_To_Flip % Total_Number_of_Counter_Bits
在每个事件发生时执行。
否则，使用二进制反射格雷码和 4 字节基 2 计数器n，...
方法 1 - 使用表格 */
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] ) ) ) ];
}
/方法 2 - 没有表格 */
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 和 Cargo Cult Coders 无需进一步阅读。
上述代码的执行效率取决于n[0], n[1], ...
在编译时计算为固定地址的事实，这是非常传统的。此外，使用按需调用优化编译器将加速数组内容，因此只需要计算一个索引值。这种编译器的复杂性可能会丢失，但很容易手动组装原始机器代码来完成它（基本上是一个开关、计算的 goto 等）。
使用孤立代码对上述算法的分析表明，每个函数调用都将执行完全相同的指令序列，无论是否优化。
在这两种方法中，非孤立返回都需要处理计数器翻转为 0 的情况，因此需要使用额外的索引和逻辑 ( !) 操作。这个额外的发生在 1/2 的 1/2 的 1/2 或总计数的 1/8 中，对于这个 1/8 中的一个计数，除了返回 31 之外别无他法。
第一种方法需要 2 次逻辑运算 ( ! ||)、1 次加法和 3 次索引计算，占总数的 7/8。在一次计数为零时，需要 3 次逻辑和 3 次索引操作，其余 1/8 需要 3 次逻辑、1 次加法和 4 次索引操作。
方法 2 执行的最终代码（优化编译），对于 7/8 的计算，使用 7 个逻辑运算（|| & ! < -最后一个是二进制补码）、1 个算术 ( +) 和 5 个计算索引运算。另一个 1/8，但是一个实例，需要 8 个逻辑、1 个加法和 6 个计算索引操作。
不幸的是，没有一丝神圣的灵感出现任何货物代码。这是一个关于这首作品的作者身份如何发生的简短故事。
这是如何完成的涉及一项重要的初步调查，如记录：
https ://stackoverflow.com/a/42846062 。
然后，使用从本文中的算法评估开始的连续细化过程得出代码。
具体来说，这个答案：https ://stackoverflow.com/a/4657711 。
通过将返回计算减少到单个加法和两个索引操作，该算法的循环开销的时变执行将得到显着的强调。
*/
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] ] ;
} }
/*
方法 2 有一个可比较的年表。
该序列已被彻底削弱并缩写为一个中间示例：
无意中，发布在https://stackoverflow.com/a/42865348中的代码并不是预期的唯一字节大小的代码。预期的代码在这篇文章中。*/
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] );
} }
/*
修辞上，我如何找到...的答案只能在个人意义上明确回答（请参阅此答案：https ://stackoverflow.com/a/42846062 ），因为无法代表其他人' 认知能力。
https://stackoverflow.com/a/42846062的内容对于背景信息至关重要，并反映了心理体操解决此问题所需的非常个人化的迂腐机制。毫无疑问，环境和过多的材料令人生畏，但这正是个人在获得足够的洞察力、曲目、轶事先例等方面所采取的方法，以推断和插入答案以具体回答 什么节目符合标准，确切地说。此外，正是这种“追逐”激发并激发了（也许是病态的）心灵投入时间和精力来用好奇的探索来满足好奇心。*/
void setup() { }
void loop() { }
/*
不能编辑以前的答案，根据评论，所以发布重写：
太不耐烦了？
为了立即获得满足和最小的启发，切入正题并追逐仅发布最终结果的此链接：
C code for generate next bit to flip in a gray code
REFs：
用于生成下一位以翻转格雷码的 C 代码
如何在恒定时间内找到下一位以更改格雷码？
从第 (n-1) 个格雷码导出第 n 个格雷码
格雷码增量函数
迭代格雷码变化位置的有效方法
生成格雷码。
https://en.wikipedia.org/wiki/The_C_Programming_Language
https://en.wikipedia.org/wiki/The_Elements_of_Programming_Style
警告：
为了方便编码和可证明的功能执行，已经使用了一些重要的编程技术。但是，希望通过 / / / / 突出显示尽可能琐碎和最小化的本质来缓解概念雏形的阐述。鼓励仔细阅读、研究和实验，以避免货物崇拜编码、疏忽和犯错。
这个答案体现在 Arduino IDE ESP8266 核心编码环境中。
OP 提出的算法并不完全正确（好像这样；）。
约翰逊密码
-------------
由于实际的格雷码是无关紧要的，因此使用约翰逊计数器的格雷码是一种非常简单和令人心酸的方式来认知和计算计算要更改的位和下一个码。
请注意，约翰逊计数器格雷码密度是线性的，而不是对数的。
使用 4 个字节中的 32 位，序列可以在复位之前从 0 计数到 63。
有必要仔细验证后面代码的功能适用性，并进行适当的修改。
提示：验证是必须的，尤其是对于“二进制反射”格雷码 (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
);
}
/*
输出：
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.
二进制反射格雷码 (BRGC) 的一些背景资料
-------------------------- -------------------------------------------------- --------
转换：
---------
REF：代码高尔夫：格雷代码
// 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";
计数：
-----------------
以下（根据上面的参考）任意获取代码的前面和后面的 BRGC。
注意！n1和的顺序n2是奇偶性确定的，否则不对应。排序可能是n1, gray, n2OR 它可能是n2, gray, n1，因此，eo（奇偶校验）是有区别的。
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;
因此
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： 格雷码中的邻居
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
哦，是的，...计数设置位，A ^ A+1其中将具有像 000...0111..1 证明的位模式。
如何获得 2 的幂的位位置 -n参数必须设置一个位。
方法一
*/
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 ...
/*
方法二
*/
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 );}
/*
方法 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.
/*
方法四
*/
// 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.......
// |------| |------|
/*
方法 5
详情在最后。
明智地选择常量能否将其减少到只有 2 次操作？
*/
byte log2toN(byte b){ return 7 - (byte) ( 0x10310200A0018380uLL >> ( (byte)(0x1D*b) >>2 ) ) ; }
/*
测试环境
*/
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; } ) );
}
/ ================================================== =====================
警告：
-----------
OP的算法无效。
Keep binary counter A
Find B as A XOR (A+1)
Bit to change is LowestBitSet in B
如编码为：
*/
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 ; }
/*
样本输出：
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
好奇的？
-----------
下面的代码是一种非常粗略的方法，可以加快寻找合适的位压缩计数候选来计算log 2^n （以 2 为基数，即。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];
*/