如何找到恒定时间在格雷码中更改的下一位? [英] How do I find next bit to change in a Gray code in constant time?

问题描述

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

I have a small 8-bit processor which has a N-to-M decoder on some output lines - eg, for the 5 to 32 bit case, I write 00101 and bit 5 changes state. The only interface to the output is change-state, there is no read-back.

设备会快速(但随机)计数发生的事件，并应将此计数作为单个位更改"代码提供给另一台设备.输出引脚由另一台设备并行读取，并且可能根据另一台设备的决定而快速或谨慎地读取，因此计数是必需的.

The device counts rapidly (but randomly) occuring events, and should provide this count as a 'single bit changes' code to another device. The output pins are read in parallel by another device, and may be read as rapidly or as sparingly as the other device decides, so the count is necessary.

我不需要使用标准的二进制反光格雷代码-我可以使用任何单位更改代码.

I do NOT need to use the standard Binary Reflective Gray code - I can use any single-bit changing code.

但是，我希望能够跟踪下一个有效更改的地方.

However, I want to be able to track the next bit to change efficiently.

我没有"LowestBitSet"指令，并且在四个8位寄存器中查找最低位设置非常耗时-因此，我无法使用这种通用"方法:

I do not have a "LowestBitSet" instruction, and finding lowest bit set across four 8 bit registers is cycle consuming - so I cannot use this "common" approach:

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

我希望在尽可能少的内存和寄存器中进行计算，并且对于任何较大的查找表，内存绝对太受限制.循环时间是更重要的因素.

I wish to calculate this in as little memory and registers as possible, and memory is definitely too restricted for any large lookup table. Cycle time is the more important factor.

对算法有何建议?

推荐答案

您不需要计算格雷码并对其进行异或，您可以只使用计数器本身，然后使用256个元素的查找表进行计数尾随零的数量.像这样:

You don't need to calculate the Gray codes and xor them, you can just use the counter itself, and then use a 256-element lookup table to count the number of trailing zeros. Like this:

unsigned char bit_change(unsigned char counter[4]) {
  static const unsigned char ones[] = {
    0,0,0,1,0,1,1,2,0,1,1,2,1,2,2,3,0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
    0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
    0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
    0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
    2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,    
  };

  unsigned char i;
  for (i = 0; i < 4; i++) {
    unsigned char x = counter[i];
    if (x) {
      x ^= x - 1;
      return 8 * i + ones[x];
    }
  }
}

如果展开循环，最多增加2个，1个xor和5个负载(但几乎总是更少).如果该表没有256个字节，则可以对半字节使用相同的策略.

If you unroll the loop, this is at most 2 adds, 1 xors, and 5 loads (but almost always less). If you don't have 256 bytes for the table, you could use the same strategy on nibbles.

这篇关于如何找到恒定时间在格雷码中更改的下一位?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！