我有一个小型的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
我希望能够在尽可能少的内存和寄存器中计算，而且内存绝对不能用于大型查找表。周期时间是更重要的因素。
有什么算法建议吗？
你不需要计算格雷码并对它们进行异或运算，你可以直接使用计数器本身，然后使用一个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字节的表格，您可以使用相同的策略在4位数上。
LowestBitSet(A ^ (A+1))总是为0，除非你在IBM工作。我认为你的意思是HighestBitSet()，它大致相当于log_2()。{ 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, ... }。我一直在努力理解算法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值。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://dev59.com/t2445IYBdhLWcg3w5OEH#4657711 不是恒定时间，因为条件测试if (x)可以根据counter[i]的值从1到4次执行而变化。 这将改变计算位数所需的时间量。
任何单个计算可能具有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 执行，则可以像位运算 & 与常量 2^n - 1 的 n-1 位一样简单）。还有一个递增。
通过将前一个代码与所需位进行异或并选择左移1到位数位置生成实际的约翰逊格雷码（JGC）序列。根据 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://dev59.com/t2445IYBdhLWcg3w5OEH#42846062
/*
如之前发布的答案https://dev59.com/t2445IYBdhLWcg3w5OEH所述，
使用约翰逊计数器格雷码非常简单：
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] ) ) ) ];
}
/方法二 - 无需表格 */
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] ] ;
}
/*
对于比特兔和货物崇拜者来说，无需继续阅读。
上述代码的执行效率取决于 n[0], n[1], ... 作为固定地址在编译时计算出来，这是相当常规的。此外，使用按需调用优化编译器将加快数组内容，因此只需要计算一个索引值。这种编译器的复杂性可能会缺失，但手动组装原始机器代码很容易实现（基本上是一个 switch、computed goto 等）。
使用孤立代码分析上述算法表明，每个函数调用都将执行完全相同的指令序列，无论是否经过优化。
在两种方法中，非孤立返回需要处理当计数器回滚到 0 时的情况，因此需要使用额外的索引和逻辑 (!) 操作。这种额外操作发生在总计数的 1/2 的 1/2 的 1/2 或 1/8 中，而在这 1/8 中的一次计数中，除了返回 31 外，没有其他操作可做。
! ||），1个加法和3个索引计算来处理总数的7/8。在仅有一个计数为零时，需要3个逻辑和3个索引操作，并且其余的1/8需要3个逻辑、1个加法和4个索引操作。|| & ! < - 最后一个是二进制补码）、1个算术运算符（+）和5个计算的索引操作。但还有1/8的情况，除了一个实例之外，需要8个逻辑、1个加法和6个计算的索引操作。这是如何完成的，需要进行关键性的初步调查，具体记录在此:
https://dev59.com/t2445IYBdhLWcg3w5OEH#42846062.
然后使用连续的细化过程派生出代码，
首先评估了该帖子中的算法。
具体来说，是这个答案: https://dev59.com/t2445IYBdhLWcg3w5OEH#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://dev59.com/t2445IYBdhLWcg3w5OEH#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://dev59.com/t2445IYBdhLWcg3w5OEH#42846062），因为不可能代表其他个体的认知能力发言。
https://dev59.com/t2445IYBdhLWcg3w5OEH#42846062的内容对于背景信息至关重要，反映了解决这个问题所需的非常个人化的追求完美机制。毫无疑问，环境和大量材料是令人生畏的，但这正是获取足够洞察力、库存、轶事先例等的个人方法，以推断和插值出一个特定的答案，即“哪个程序完全符合标准”。此外，正是这种“追逐”激发和激励着（也许是病态的）心理投入时间和精力，以满足好奇心的探究之旅。 */
void setup() { }
void loop() { }
/*
无法编辑之前的答案，根据评论，所以发布改写版本：
太心急了吗？
为了即时满足和最小化教育，切入正题并跟踪此链接，
只有最终结果已发布：
用于生成下一个要翻转的比特位的 C 代码
REFs：
用于生成下一个要翻转的比特位的 C 代码
如何在恒定时间内找到格雷码中要更改的下一个比特位？
从(n-1)th Gray Code推导出第n个Gray Code
Gray Code增量函数
高效迭代Gray Code变化位置的方法
生成Gray Code。
https://en.wikipedia.org/wiki/The_C_Programming_Language
https://en.wikipedia.org/wiki/The_Elements_of_Programming_Style
警告：
为了编码迅速和可演示的功能执行，使用了一些非平凡的编程技术。然而，通过以尽可能简单和最小化的方式呈现本质，并用 / / / / 强调概念基础知识，希望能够缓解这种情况。鼓励仔细阅读、学习和实验，以避免盲目模仿编码、疏忽和犯错。
此答案在Arduino IDE ESP8266核心编码环境中体现。
正如提问者所述，算法并不完全正确（就像这样;）。
约翰逊码
-------------------------
由于实际的格雷码是无关紧要的，使用约翰逊计数器的格雷码是一种非常简单和深刻的认知和计算方法，可以计算出要更改的位和下一个代码。
请注意，约翰逊计数器的格雷码密度是线性的，而不是对数的。
使用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）的一些背景材料
-----------------------------------------------------------------------------------------------
转换：
---------------------
参考：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";
n1和n2的顺序由奇偶性确定，否则无对应关系。
排序可能是n1，gray，n2，也可能是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
即。
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 必须只有一个位集。
方法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 ...
/*
方法二
*/
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 );}
/*
方法三
*/
byte powerOf2(byte n){ return ( n & 0xF0 ? 4:0 ) + // 4444....
( n & 0xCC ? 2:0 ) + // 22..22..
( n & 0xAA ? 1:0 ) ; } // 1.1.1.1.
/*
方法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.......
// |------| |------|
/*
第五种方法
详情请见结尾。
通过明智的常数选择，能将其减少为仅需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; } ) );
}
/======================================================================
注意事项：
-----------
原帖中的算法并不有效。
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];
*/