用于生成下一位翻转格雷码的C代码 [英] C code for generating next bit to flip in a gray code
问题描述
我需要一个函数,该函数返回一个数字,从本质上讲告诉我,当移至格雷代码的第n个元素时,哪一位将成为翻转位.不管是标准(反射)格雷码还是其他一些最小的位切换方法,都没有关系.我可以做到,但似乎不必要.目前我有这个:
I need a function that returns a number essentially telling me which bit would be the one to flip when moving to the nth element of a Gray code. It doesn't matter if it's the standard (reflecting) Gray code or some other minimal bit-toggling approach. I can do it, but it seems unnecessarily unwieldy. Currently I have this:
#include <stdio.h>
int main()
{
int i;
for (i=1; i<32; i++)
printf("%d\n",grayBitToFlip(i));
}
int grayBitToFlip(int n)
{
int j, d, n1, n2;
n1 = (n-1)^((n-1)>>1);
n2 = n^(n>>1);
d = n1^n2;
j = 0;
while (d >>= 1)
j++;
return j;
}
main()中的循环仅用于演示函数的输出.
The loop in main() is only there to demonstrate the output of the function.
有更好的方法吗?
仅查看输出,很明显可以更简单地完成此操作.我添加了第二个函数gray2,它可以更简单地完成相同的操作.这会是这样做的方法吗?顺便说一下,这不是生产代码,而是爱好者.
just looking at the output, it's obvious one can do this more simply. I've added a 2nd function, gray2, that does the same thing much more simply. Would this be the way to do it? This is not production code by the way but hobbyist.
#include <stdio.h>
int main()
{
int i;
for (i=1; i<32; i++)
printf("%d %d\n",grayBitToFlip(i), gray2(i));
}
int grayBitToFlip(int n)
{
int j, d, n1, n2;
n1 = (n-1)^((n-1)>>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格雷码(JGC
).
The easiest Gray code to use is a Johnson Gray Code (JGC
).
BitNumberToFlip = ++BitNumberToFlip % NumberOfBitsInCode;
JGC = JGC ^ (1 << BitNumberToFlip); // start JGC = 0;
Johnson代码在表示所需的位数上是线性的.
二进制反射格雷码(BRGC
)具有更好的位密度,因为仅
需要一个对数位数来表示BRGC
码的范围.
A Johnson code is linear in the number of bits required for representation.
A Binary Reflected Gray Code (BRGC
) has a much better bit density since only
a logarithmic number of bits are required to represent the range of BRGC
codes.
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 ) ); }
for details see ref:
How do I find next bit to change in a Gray code in constant time?
这篇关于用于生成下一位翻转格雷码的C代码的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!