如何在常量时间内找到格雷码中的下一位？

Question

我有一个小的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 

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

关于算法的任何建议？

Answer 1

“算法 L”第 10 页Knuth, Donald E.“生成所有 n 元组”。《计算机编程的艺术》，第 4A 卷：枚举和回溯，前分册 2a，2004 年 10 月 15 日似乎很理想。对于您的设备，步骤 L4 将是“change_state(j)”。