确定字节中的哪个单位已设置

Question

我有一个byte我用于比特标志.我知道在任何给定时间都设置了一个且只有一个位byte.

例如: unsigned char b = 0x20; //(00100000) 6th most bit set

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

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

如何最有效地确定设定位的位置？我可以不经迭代地完成这项工作吗？

Answer 1

我可以不经迭代地完成这项工作吗？

这确实是可能的.

如何最有效地确定设定位的位置？

你可以试试这个算法.它将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);
}

它使用两个比较(三个用于uint16s,四个用于uint32s ...).它可能比你的循环更快.绝对不会短.

根据Anton Kovalenko的想法(散列查找)和6502的评论(除法很慢),我也建议这个实现(使用de-Bruijn序列的8位=> 3位散列)

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

Answer 2

查找表很简单,如果值集稀疏,则可以减小其大小.让我们试试11个元素而不是128个:

unsigned char expt2mod11_bits[11]={0xFF,0,1,0xFF,2,4,0xFF,7,3,6,5};
unsigned char pos = expt2mod11_bits[b%11];
assert(pos < 8);
assert(1<<pos == b);

当然,它不一定更有效,特别是对于8位,但同样的技巧可以用于更大的尺寸,其中完整的查找表将非常大.让我们来看看:

unsigned int w; 
....
unsigned char expt2mod19_bits[19]={0xFF,0,1,13,2,0xFF,14,6,3,8,0xFF,12,15,5,7,11,4,10,9};
unsigned char pos = expt2mod19_bits[w%19];
assert(pos < 16);
assert(1<<pos == w);