格雷码递增函数
在不使用任何外部计数器或其他状态的情况下，我正在寻找一个有效的函数，该函数采用n位值（32位或左右）并返回格雷码中的后续值。
那是：
int fn(int x) { int y = gray_to_binary(x); y = y + 1; return binary_to_gray(y); } 但是虽然binary_to_gray()函数是微不足道的（ x ^ (x >> 1) ），但相应的gray_to_binary()根本不是那么简单（ log(n)迭代的循环）。
也许有一个更有效的操作序列？ 对于标准reflection格雷码，或者为了解决此问题而选择的另一格雷码。
旁白：我看到这个问题有两种可能的解决方案类型 – 一种是选择一种更容易转换为二进制的代码并使用上面给出的forms（或者为了反映代码演示更有效的二进制转换），以及另一种方法是将转换推迟到二进制并生成一种方法，该方法在不使用二进制增量的情况下遍历格雷码。
在后一种情况下，将结果代码转换为二进制代码可能会变得特别困难。 从实际角度来看，这可能是一个不利因素，但它仍然是一件有趣的事情。
更新：因为有人指出灰色解码只是log(n)操作（使用两种不同技术中的任何一种），我花了一些时间试图弄清楚这是否是对事物可以简化的严格限制。 在确定要执行的下一个操作时必须考虑所有位，否则“考虑”位将无法改变，并且函数将在两个值之间振荡。 必须以某种方式将输入压缩为可管理的比例，以确定要执行的下一个操作。
为了使其成为log(nk)操作，可以使用2k -entry LUT来缩短最后的k操作（注释表明k=32 ）。
另一种可以经常减少事物的技术是乘法和位掩码的组合。 例如，计算奇偶校验以实现基于奇偶校验的算法。
从乘法和位掩码的方法来看，似乎可能有空间来发明格雷码，这进一步简化了操作集……但我不认为任何这样的代码是已知的。
一种增加格雷码的简单算法：
gray_inc(x): if parity of x is even: return x xor 1 if parity of x is odd: let y be the rightmost 1 bit in x return x xor (y leftshift 1)
找到x的奇偶校验需要O（log（k）），其中k是x的位长。 但是，上述算法中的每一步都会更改奇偶校验，因此在循环中您可以只交替奇偶校验操作。 （当然，这不符合OP要求，即不保留任何状态;它需要一点状态。另外，请参见下文。）
使用标准位攻击查找y是O（1）： y = x&-x ，其中-是2的补码否定运算符; 你也可以把它写成y = x and not (x - 1) 。
您也可以使用奇偶校验增强型格雷码，后者是带有反奇偶校验位的格雷码（因此增强码的奇偶校验总是奇数）。 在这种情况下，您可以使用以下O（1）算法：
parity_gray_increment(x): let y be the rightmost bit in x return x xor ((y leftshift 1) or 1)
在上述两种算法中，为了清楚起见，我省略了溢出检查。 要使代码循环溢出， y leftshift 1 if y is not the high-order bit, else y y leftshift 1替换为y leftshift 1 y leftshift 1 if y is not the high-order bit, else y 。 （在大多数体系结构中， if y leftshift 1 is not 0 ，则测试可能是。）或者， if y leftshift 1 is not 0 ，则可能抛出exception或返回错误。
根据你的目标，我有三种方式可以使用。
1）一个常见function：编写一个函数来处理您需要支持的最宽泛的格雷码值。 遵循@harold建议使用更大的变化和xors的方法：
inline UInt16 graycodeToBinary( UInt16 value ) { value ^= (value >> 1); value ^= (value >> 2); value ^= (value >> 4); value ^= (value >> 8); return value; }
根据需要扩展输入数据类型和移位，直到下一个移位量等于或超过数据位数。 即使设置和测试一个循环也不如运行这些指令有效。 这只会比查找方法稍慢。
2）每个幂的function为2与上面相同，但使用graycodeToBinary_8，_16，_32版本。 如果你做了很多小的转换，偶尔会有很大的转换，这样做会很有用。 如果使用C ++重载可以自动为您选择合适的版本（并且您可以通过一些模板元编程将其变为荒谬）。
3）查找表：除非你考虑缓存行为，否则这似乎是一个好主意。 如果您不经常使用查找表，那么与上述方法相比，它是不必要的复杂。 如果您经常使用查找表，它可能会破坏您的缓存行为（大量分散读取到更大的内存区域）。 有一小部分应用程序会变得非常快。 此外，您必须创建查找表，因此您可能已经可以使用graycode_to_binary函数。
最后，除了选项1），我很少找到任何用途。 我见过一个嵌入式应用程序，它将查找表硬编码到它的ROM中。 这很好，因为处理器还没有缓存。
我在C＃中实现了一个似乎有效的算法：
首先，您需要整数的奇偶校验。 我已经为ulong （64位）实现了它，但您可以轻松地将其修改为任何所需的输出：
public static ulong GetParity (ulong value) { value ^= value >> 0x20; value ^= value >> 0x10; value ^= value >> 0x08; value ^= value >> 0x04; value &= 0x0f; return (0x6996UL >> (int)value) & 0x01; }
接下来，您需要检查奇偶校验是否为偶数（设置的位数是偶数，如果是这种情况，则只需交换最后一位）。 如果奇偶校验是奇数，则通常将最低有效设置位左侧的位交换。 这可以使用以下方法计算：
public static ulong LeastSignificantBit (ulong value) { return value&((~value)+0x01); }
有一个边界情况：如果最低有效设置位是格雷码的最大位，如果是这种情况，你当然可以不交换左位，你只需将计数器设置为零。
总而言之，您可以使用以下代码：
public static ulong GrayIncrement (ulong original, int bits = 0x40) { ulong last = 0x01UL << (bits - 0x01); if (GetParity (original) == 0x00) { return original ^ 0x01UL;//even parity: swap least significant bit } else { ulong lbm = LeastSignificantBit(original); if (lbm < last) { return original ^ (lbm << 0x01);//otherwise swap the bit left to the least significant set bit } else { return 0x00;//wrap around } } }
来自wiki（ http://en.wikipedia.org/wiki/Gray_code#Converting_to_and_from_Gray_code ）
/* The purpose of this function is to convert an unsigned binary number to reflected binary Gray code. The operator >> is shift right. The operator ^ is exclusive or. */ unsigned int binaryToGray(unsigned int num) { return (num >> 1) ^ num; } /* The purpose of this function is to convert a reflected binary Gray code number to a binary number. */ unsigned int grayToBinary(unsigned int num) { unsigned int mask; for (mask = num >> 1; mask != 0; mask = mask >> 1) { num = num ^ mask; } return num; }