用于生成下一位翻转格雷码的C代码

本文介绍了用于生成下一位翻转格雷码的C代码的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我需要一个函数，该函数返回一个数字，从本质上讲告诉我，当移至格雷代码的第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 ) ); }

有关详细信息，请参见ref: 如何找到恒定时间的格雷码中要更改的下一位?

for details see ref: How do I find next bit to change in a Gray code in constant time?