用于生成下一位以在灰色代码中翻转的C代码
我需要一个函数返回一个数字,基本上告诉我在移动到格雷码的第n个元素时哪个位是要翻转的。 如果它是标准(reflection)格雷码或其他一些最小位切换方法并不重要。 我可以做到,但似乎不必要的笨拙。 目前我有这个:
#include int main() { int i; for (i=1; i>1); n2 = n^(n>>1); d = n1^n2; j = 0; while (d >>= 1) j++; return j; }
main()中的循环仅用于演示函数的输出。
有没有更好的办法?
编辑:只看输出,显然可以更简单地做到这一点。 我添加了第二个函数gray2,它可以更简单地完成相同的操作。 这会是这样做的吗? 这不是生产代码,而是业余爱好者。
#include int main() { int i; for (i=1; i>1); n2 = n^(n>>1); d = n1^n2; j = 0; while (d >>= 1) j++; return j; } int gray2(int n) { int j; j=0; while (n) { if (n & 1) return j; n >>= 1; j++; } return j; }
最简单的格雷码是Johnson Gray Code( JGC
)。
BitNumberToFlip = ++BitNumberToFlip % NumberOfBitsInCode; JGC = JGC ^ (1 << BitNumberToFlip); // start JGC = 0;
Johnson代码在表示所需的位数方面是线性的。
二进制reflection格雷码( BRGC
)具有更好的比特密度,因为仅需要对数比特来表示BRGC
码的范围。
int powerOf2(int n){ return // does 16 bit codes ( n & 0xFF00 ? 8:0 ) + // 88888888........ ( n & 0xF0F0 ? 4:0 ) + // 4444....4444.... ( n & 0xCCCC ? 2:0 ) + // 22..22..22..22.. ( n & 0xAAAA ? 1:0 ) ; } // 1.1.1.1.1.1.1.1. // much faster algorithms exist see ref. int BRGC(int gc){ return (gc ^ gc>>1);} int bitToFlip(int n){ return powerOf2( BRGC( n ) ^ BRGC( n+1 ) ); }
有关详情请参阅参考:
如何在常数时间内找到格雷码中的下一位?