c - 确定设置了字节中的哪一位

Question

我有一个 byte 用于位标志。我知道 byte 中的one and only one 位是在任何给定时间设置的。

例如:unsigned char b = 0x20;//(00100000) 第 6 位设置

我目前使用以下循环来确定设置了哪个位:

int getSetBitLocation(unsigned char b) {
  int i=0;
  while( !((b >> i++) & 0x01) ) { ; }
  return i;
}

如何最有效地确定设置位的位置？我可以在没有迭代的情况下做到这一点吗？

Answer 1

Can I do this without iteration?

确实有可能。

How do I most efficiently determine the position of the set bit?

你可以试试这个算法。它将 char 分成两半以搜索最高位，每次都转移到低半部分:

int getTopSetBit(unsigned char b) {
  int res = 0;
  if(b>15){
    b = b >> 4;
    res = res + 4;
  }
  if(b>3){
    b = b >> 2;
    res = res + 2;
  }

  //thanks @JasonD
  return res + (b>>1);
}

它使用两个比较(三个用于 uint16，四个用于 uint32...)。它可能比你的循环更快。它绝对不会更短。

---

基于 Anton Kovalenko 的想法(哈希查找)和 6502 的评论(除法很慢)，我还建议这个实现(8 位 => 3 位哈希使用 de-Bruijn 序列)

int[] lookup = {7, 0, 5, 1, 6, 4, 3, 2};

int getBitPosition(unsigned char b) {
  // return lookup[(b | (b>>1) | (b>>2) | (b>>4)) & 0x7];
  return lookup[((b * 0x1D) >> 4) & 0x7];
}

或(更大的 LUT，但只使用三个项而不是四个)

int[] lookup = {0xFF, 0, 1, 4, 2, 0xFF, 5, 0xFF, 7, 3, 0xFF, 0xFF, 6, 0xFF, 0xFF, 0xFF};

int getBitPosition(unsigned char b) {
  return lookup[(b | (b>>3) | (b>>4)) & 0xF];
}