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

Question

我有一个用于位标志的字节。我知道一个且只有一个位在字节中在任何给定时间被设置。

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

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

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?

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

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];
}