Tag: 灰码

格雷码中的邻居

我可以使用任何算法在格雷码中找到邻居吗？ 对于小数字来说，编写整个表格就好了，但是如果我有一个像010这样的数字，那么用6个数字编写整个灰色代码表有点太多了。

格雷码递增函数

在不使用任何外部计数器或其他状态的情况下，我正在寻找一个有效的函数，该函数采用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 ）。 另一种可以经常减少事物的技术是乘法和位掩码的组合。 例如，计算奇偶校验以实现基于奇偶校验的算法。 从乘法和位掩码的方法来看，似乎可能有空间来发明格雷码，这进一步简化了操作集……但我不认为任何这样的代码是已知的。