如何在常量时间内找到格雷码中的下一位？
我有一个小的8位处理器，在某些输出线上有一个N对M解码器 - 例如，对于5到32位的情况，我写00101和位5改变状态。输出的唯一接口是change-state，没有回读。
设备快速（但随机）发生事件计数，并应将此计数作为“单个位更改”代码提供给另一个设备。输出引脚由另一个器件并行读取，并且可以像其他器件决定的那样快速或少量地读取，因此计数是必要的。
我不需要使用标准的Binary Reflective Gray代码 - 我可以使用任何单位更改代码。
但是，我希望能够跟踪下一位有效更改的位。
我没有“LowestBitSet”指令，并且在四个8位寄存器中找到最低位设置是循环消耗 - 所以我不能使用这种“常见”方法：
Keep binary counter A
Find B as A XOR (A+1)
Bit to change is LowestBitSet in B
没有找到相关结果
已邀请:
7 个回复
掀辟髓观粟
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]; } } }渐首洽陈染
期差骇蓟
n = lastCode = 0 increment: n+=1 newCode = GrayCode(n) delta = newCode XOR oldCode bitToToggle = BitIndex(delta) old code = new code GOTO increment;逝媳蘑贩茄
始终为0。我认为你的意思是，与大致相同。 紧接着由AShelly连接的那个之前的比特笨拙的黑客在8位微观上将更加可行。 这应该使你的原始算法相当实用，产生{ 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, ... }澜悍景哭苟
可以在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) ); }操作 即。常数）和增量。 实际的约翰逊格雷码（JGC）序列是通过前面的代码逐步生成的 通过左移1到位数位置选择所需的位。 根据OP的要求，不需要这种计算。 约翰逊法典 ------------------------- 实际的格雷编码是无关紧要的，因此使用约翰逊计数器的格雷码非常简单。 请注意，约翰逊格雷码（JGC）密度是线性的，而不是像2或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("ntJohnson countert Bitnt 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 ); }郸身
在每次事件发生时执行。 否则，使用二进制反射格雷码和4字节基2计数器，... 方法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] ] ; }的事实 在编译时计算为固定地址，这是非常传统的。 此外，使用按需调用优化编译器将加快数组内容 所以只需要计算一个索引值。 这种编译器的复杂性可能会丢失，但很容易手动组装 这样做的原始机器代码（基本上是一个开关，计算goto等）。 使用孤立代码分析上述算法，显示每个函数 call将执行完全相同的指令序列，优化与否。 在这两种方法中，非孤立的返回需要在那里处理案例 计数器在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个逻辑运算（，最后是2的补码）， 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] ] ; } }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] ); } }void setup() { } void loop() { }递劝臼类洪
警告： 为了编写权宜之计和可证明的功能执行， 已经使用了一些非平凡的编程技术。但是，这是 希望减轻对概念基础的阐述 通过尽可能简单和最低限度地展示本质 突出显示/ / / /。鼓励仔细阅读，学习和实验 避免货物编码，疏忽和犯错误。 这个答案体现在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("ntJohnson countert Bitnt 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.// 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";和的顺序是奇偶校验确定的，否则不相应。 排序可能是或者它可能是，因此，（奇偶校验）可以区分。即。于是/ / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / /。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哦是的，...计算中的位设置，它将具有类似000 ... 0111..1 Prove的位模式。 如何获得2的幂的位位置 -参数必须设置一个位。 方法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.// 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....... // |------| |------|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; } ) ); }编码为： * /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 " "nn 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（在基数2即.19ѭ）。 * /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];