标签: gray-code

挑战

输出n位格雷码的字符数最短的程序.n将是一个小于(由于用户建议)从标准输入中获取的任意数字.格雷码将以标准输出打印,如示例中所示.1000100000

注意:我不希望程序在合理的时间内打印格雷码(n=100000过度杀伤); 我确实希望它开始打印.

例

输入:

4

预期产出:

0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000

有没有任何已知的方法来计算两个格雷码的加法(也许是减法),而不必将两个格雷码转换为常规二进制,执行二进制加法然后将结果转换回格雷码？我设法编写递增和递减函数,但加法和减法似乎记录更少,更难写.

不使用任何外部计数器或其他状态,我正在寻找一个有效的函数,它取一个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)迭代循环).

也许有一个更有效的操作序列？要么是标准反射格雷码,要么选择其他格雷码以适应这个问题.

旁白: 我看到这个问题有两种可能的解决方案类型 - 一种是选择一种更容易转换为二进制的代码并使用上面给出的形式(或者为了反映代码演示更有效的二进制转换),以及另一种方法是将转换推迟到二进制并生成一种方法,该方法在不使用二进制增量的情况下遍历格雷码.

在后一种情况下,将结果代码转换为二进制代码可能会变得特别困难.从实际角度来看,这可能是一个不利因素,但它仍然是一件有趣的事情.

更新: 因为有人指出灰色解码只是log(n)操作(使用两种不同技术中的任何一种),我花了一些时间试图弄清楚这是否是对事物可以简化的严格限制.在确定要执行的下一个操作时必须考虑所有位,否则"考虑"位将无法改变,并且函数将在两个值之间振荡.必须以某种方式将输入压缩到可管理的比例以确定要执行的下一个操作.

为了使其log(n-k)运行,可以使用2 ^k -entry LUT来缩短最后的k操作(评论建议k=32).

另一种可以经常减少事物的技术是乘法和位掩码的组合.例如,计算奇偶校验以实现基于奇偶校验的算法.

从乘法和位掩码的方法来看,似乎可能有空间来发明格雷码,这进一步简化了操作集......但我不认为任何这样的代码是已知的.

我有一个小的8位处理器,在某些输出线上有一个N对M解码器 - 例如,对于5到32位的情况,我写00101和位5改变状态.输出的唯一接口是change-state,没有回读.

设备快速(但随机)发生事件计数,并应将此计数作为"单个位更改"代码提供给另一个设备.输出引脚由另一个器件并行读取,并且可以像其他器件决定的那样快速或少量地读取,因此计数是必要的.

我不需要使用标准的Binary Reflective Gray代码 - 我可以使用任何单位更改代码.

但是,我希望能够跟踪下一位有效更改的位.

我没有"LowestBitSet"指令,并且在四个8位寄存器中找到最低位设置是循环消耗 - 所以我不能使用这种"常见"方法:

  Keep binary counter A
  Find B as A XOR (A+1)
  Bit to change is LowestBitSet in B 

我希望在尽可能少的内存和寄存器中计算它,并且对于任何大型查找表来说内存肯定是太受限制了.周期时间是更重要的因素.

关于算法的任何建议？

计算第n个格雷码的公式为:

(n-1) XOR (floor((n-1)/2))  
(Source: wikipedia)

我把它编码为:

int gray(int n)
{
  n--;
  return n ^ (n >> 1);
}

有人可以解释上述公式是如何工作的,或者可能是它的推导？

我尝试构建一个结构化的光环境来进行3D扫描.

据我所知,如果我选择使用格雷码来重建3D模型,我必须实现在幂2(2 ^ x,x = 0~10)中编码的特定模式.

也就是说,模式的分辨率必须至少为1024 x 1024.

如果我的DLP投影机仅支持高达800 x 480的分辨率怎么办？当灰色代码模式分辨率变得太高时,它会投射莫尔图案(我试过).我该怎么办？

我的朋友们建议我创建1024 x 1024个图案,并将它们"裁剪"成800 x 480,

但是我认为灰色代码应该遵循特定的顺序和模式,我的朋友建议会创建几个不对称的图像.

有没有人像我一样拥有相同的经历？

---------- 2015.8.4更新问题----------

我想如果我的投影机无法完美地投射高分辨率图案,我可以让它以低分辨率投影图案,例如,从2 ^ 0到2 ^ 6？

或者格雷码严格要求从2 ^ 0到2 ^ 10的模式？否则灰色代码不可用？

在.NET框架中的任何地方都有内置的格雷码数据类型吗？或者Gray和binary之间的转换实用程序？我可以自己做,但如果轮子已经发明了......

我试图找到给出两个数字的问题的解决方案,找出它们是否是灰色代码序列中的连续数字,即,如果它们是灰色代码邻居,假设没有提到格雷码序列.

我在各种论坛上搜索但无法得到正确的答案.如果您能为此提供解决方案,那就太好了.

我试图解决这个问题 - 将两个整数转换为二进制并分别在两个数字中加上数字,并找出两个数字中数字之和的差值.如果差异是1,则它们是格雷码邻居.

但我觉得这不适用于所有情况.任何帮助都非常感谢.非常感谢提前!

我正在尝试实现一种算法，从一组 n 个元素中获取 k 个元素的所有组合，其中两个连续组合之间的差异最大化（类似于反向格雷码）。换句话说，应该对组合进行排序以避免元素连续出现两次，这样就不会不必要地歧视任何元素。

理想情况下，该算法也不会预先计算所有组合并将它们存储到内存中，而是按需提供组合。我对此进行了广泛的搜索，并找到了一些详细的答案，例如/sf/answers/8949951/，但我似乎无法应用它。此外，该答案中链接的许多文章都是付费内容。

为了说明我的意思：

从一组 [0, 1, 2, 3, 4] 中，找到两个元素的所有组合。使用一个简单的算法，尝试增加最右边的元素，直到不再可能，然后向左移动，增加前一个数字等，我得到以下结果：

[0, 1]
[0, 2]
[0, 3]
[0, 4]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]

我使用以下 Java 代码生成此结果：

public class CombinationGenerator {
    private final int mNrElements;
    private final int[] mCurrentCombination;

    public CombinationGenerator(int n, int k) {
        mNrElements = n;
        mCurrentCombination = new int[k];

        initElements(0, 0);
        // fake initial state in order not to miss first combination below
        mCurrentCombination[mCurrentCombination.length - …

对于通信系统,我需要一种特殊的格雷码.要求是:

1. 与所有格雷码一样,两个连续值仅在一位上不同.
2. 同一位上的两个转换应至少远离某些任意数量的值.最小行程长度为mrl.
3. 我不关心从最后一个代码到第一个代码的距离,当代码翻转时mrl没有约束.

这种格雷码的一个例子是,对于5位且mrl = 4:

01111000011110000111100001111000
00111100000011111100001111110000
00011110000111100001111000011110
00001111110000111111000000111100
00000000111111110000000011111111

本文给出了不同位数的最佳mrl值.然后,通过使用详尽的计算机搜索找到这些值.

我有python代码,适用于少量位,最多6位:

N = 5 # number of bit
mrl = 4 # minimum run length
first_transition = [0]
first_code = [0]

def Recur(previous_transitions, previous_codes):
  if len(previous_codes) == (2**N):
    for b in xrange(N):
      print ''.join([str((code >> (N-b-1)) & 1) for code in previous_codes])
    print
    return
  new_transition_list = range(N)
  for new_transition in new_transition_list:
    ok = True
    for i in xrange(mrl-1): #look back for transitions that are too close …