不使用任何外部计数器或其他状态,我正在寻找一个有效的函数,它取一个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
我希望在尽可能少的内存和寄存器中计算它,并且对于任何大型查找表来说内存肯定是太受限制了.周期时间是更重要的因素.
关于算法的任何建议？
我试图找到给出两个数字的问题的解决方案,找出它们是否是灰色代码序列中的连续数字,即,如果它们是灰色代码邻居,假设没有提到格雷码序列.
我在各种论坛上搜索但无法得到正确的答案.如果您能为此提供解决方案,那就太好了.
我试图解决这个问题 - 将两个整数转换为二进制并分别在两个数字中加上数字,并找出两个数字中数字之和的差值.如果差异是1,则它们是格雷码邻居.
但我觉得这不适用于所有情况.任何帮助都非常感谢.非常感谢提前!