确定字节中哪个单个位被设置。

Question

我有一个用于位标志的byte。我知道在任何给定时间，byte 中只有一个比特被设置。

例如：unsigned char b = 0x20; //(00100000) 第6个最高位被设置 我目前使用以下循环来确定哪个比特被设置：

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

如何最有效地确定位设置的位？我能否在不迭代的情况下完成这个操作？

- recursion.ninja

---

假设一个字节为8位，使用查找表可能会有所帮助，除非您可以利用“计算前导零”原语/指令。 - Brett Hale

我能不用迭代来完成这个吗？使用查找表或者 switch 语句。 - David Heffernan

你可以进行三次比较和一些数学计算。它是否真的比这个循环更快？很难说。 - John Dvorak

@JanDvorak 什么是三种比较/数学运算？ - recursion.ninja

如果这是你的瓶颈，那么你就无法击败查找表。我猜你实际上还没有进行任何分析，并且没有得到优化的好处。 - David Heffernan

Answer 1

我能不使用迭代完成这个任务吗？

确实有可能。

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

您可以尝试这个算法。它将字符一分为二，搜索顶部位，每次将其移动到低半部分：

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

或者（更大的查找表，但只使用三个术语而不是四个）

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

- John Dvorak

---

你可以移除最后一个if()，只需将b-1添加进去。 - JasonD

@JanDvorak 很聪明，这可能会更有效率。 - recursion.ninja

@JanDvorak 他说只有1个比特被设置，所以它应该只是1或2。不过你的替代方案更加通用。 - JasonD

@JanDvorak，您的哈希查找表lookup [((b * 0x1D) >> 4)＆0x7]；在检查仅设置了一位时通过了我的8个字节测试用例{ 0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80 }。非常优雅！我可以问一下您从哪里获取了哈希吗？您能链接到德布鲁因序列吗？ - recursion.ninja

很酷的技巧！我一直使用类似于lut[foo％67]的东西，将foo转换为log2（foo），当foo是2的幂时。 - tmyklebu

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);

- Anton Kovalenko

---

更大的尺寸是个好主意……但对于8位来说，我想取模运算会成为一个问题。 - 6502

在x86上，我会尝试使用BSF内联汇编。 - Anton Kovalenko

@AntonKovalenko 除了模11是跨平台的，而BSF不是。 - John Dvorak

@JanDvorak：你有点过于乐观了。除法一直是非常慢的...慢到设计第一款奔腾处理器时，他们甚至试图省略一些步骤；如果你需要商，除法在许多情况下可以被换成乘法，但如果你需要余数，这个技巧就不起作用了。而且据我所知，即使是整数乘法，在我使用的任何处理器上也需要2个周期。 - 6502

@JanDvorak 这段内容无法适应评论区，但它以780903145的乘法开始。请注意，该数字恰好为“0x200000003 / 11”。 - user743382

Answer 3

这是棋类程序中常见的一个问题，使用64位来表示位置（即用一个64位数字存储全部白兵位置，另一个存储全部黑兵位置，等等）。

由于这种表示方法有时需要找到第一个或最后一个设置位的索引（0...63），因此有几种可能的方法：

1. 只是像您所做的那样循环
2. 使用二分搜索（即如果x & 0x00000000ffffffffULL为零，则无需检查低32位）
3. 如果处理器支持，则使用特殊指令（例如，在x86上使用bsf和bsr）
4. 使用查找表（当然不是针对整个64位值，而是针对8或16位）

但是，真正更快的方式取决于您的硬件和实际使用情况。对于仅有8位且使用现代处理器的情况下，我认为一个具有256个条目的查找表可能是最好的选择...

但是，您真的确定这是算法的瓶颈吗？

- 6502

---

"...FULL" 的意思是“无符号长长整型（unsigned long long）”吗？ - John Dvorak

ULL是后缀，F只是最后一个十六进制数字，我会进行编辑以使其更清晰。 - 6502

我的意思是，它是否可以编译，还是只是一个占位符/省略号 :-) - John Dvorak

Answer 4

unsigned getSetBitLocation(unsigned char b) {
  unsigned pos=0;
  pos = (b & 0xf0) ? 4 : 0; b |= b >>4;
  pos += (b & 0xc) ? 2 : 0; b |= b >>2;
  pos += (b & 0x2) ? 1 : 0; 
  return pos; 
}

这很难不出现跳跃。也许可以用Bruin序列来解决？

- wildplasser

Answer 5

基于在 【寻找N位整数的log2值】一文中的log2计算：

int getSetBitLocation(unsigned char c) {
  // c is in {1, 2, 4, 8, 16, 32, 64, 128}, returned values are {0, 1, ..., 7}
  return (((c & 0xAA) != 0) |
          (((c & 0xCC) != 0) << 1) |
          (((c & 0xF0) != 0) << 2));
}

- jfs

---

@JanDvorak：是的，它在C99中被添加。(我使用三目运算符是为了向下兼容C89/C90) 它确实看起来不是无跳转的。(但现在有一些奇怪的指令) - wildplasser

@JanDvorak: 是的，在C99之前就已经保证了。此外，我在代码中没有看到任何分支。你可以在线查看它的汇编代码。你能指出分支指令吗？ - jfs

请注意，通过deBrujin基础解决方案可以简化为仅五个操作：MOVZB，IMUL，SAR，AND，MOV。 - John Dvorak

@JanDvorak：您可以将代码原样粘贴。在线服务接受未命名为 main() 的函数。如果禁用编译器中的优化，则担心分支是没有意义的。德布鲁因序列看起来很有趣。 - jfs

我很惊讶它没有将我的 IMUL 转换成一系列的加法。 - John Dvorak

Answer 6

最简单的方法是创建一个查找表。最简单的查找表将是稀疏的（具有256个元素），但从技术上讲，它可以避免迭代。

这里的评论从技术上避免了迭代，但是我们在愚弄谁呢？它仍然进行相同数量的检查：如何在c/c++中编写log base(2)。

封闭形式将是 log2()，即 log2() + 1，但我不确定它有多有效 - 可能CPU有一个用于取2为底的对数的指令？

- poundifdef

---

FYL2X指令与位移操作有何区别？不太确定。 - Anirudh Ramanathan

一张拥有255个元素的稀疏查找表所需的内存并不会超过对性能进行轻微优化的权衡。 - recursion.ninja

当CHAR_BIT == 16或CHAR_BIT == 32时，一个稀疏查找表会有多少个元素？ - autistic

“可能CPU有一个取2为底的对数的指令？” 大多数处理器都有一个计算前导零的指令。 - Pascal Cuoq

Answer 7

如果你定义了

const char bytes[]={1,2,4,8,16,32,64,128}

并使用

struct byte{
char data;
int pos;
}
void assign(struct byte b,int i){

b.data=bytes[i];
b.pos=i
}

你不需要确定集合位的位置

- woryzower

---

你不需要确定集合位的位置 -- 我想提出质疑 - John Dvorak

他正在解决相反的问题...给定值找到索引。扫描表格就像检查位一样简单。 - 6502

Answer 8

当CHAR_BIT == 8时，查找表快速且容易，但在某些系统上，CHAR_BIT == 16或32，查找表变得非常庞大。如果您正在考虑使用查找表，我建议将其包装; 将其制作为“查找表函数”，以便在需要优化时可以交换逻辑。

通过对排序数组执行二进制搜索，使用分治法涉及基于log2 CHAR_BIT的比较。该代码更复杂，涉及初始化unsigned char数组以用作查找表的开始。一旦初始化了这样的数组，您就可以使用bsearch来搜索它，例如：

#include <stdio.h>
#include <stdlib.h>
void uchar_bit_init(unsigned char *table) {
    for (size_t x = 0; x < CHAR_BIT; x++) {
        table[x] = 1U << x;
    }
}
int uchar_compare(void const *x, void const *y) {
    char const *X = x, *Y = y;
    return (*X > *Y) - (*X < *Y);
}
size_t uchar_bit_lookup(unsigned char *table, unsigned char value) {
    unsigned char *position = bsearch(lookup, c, sizeof lookup, 1, char_compare);
    return position ? position - table + 1 : 0;
}
int main(void) {
    unsigned char lookup[CHAR_BIT];
    uchar_bit_init(lookup);
    for (;;) {
        int c = getchar();
        if (c == EOF) { break; }
        printf("Bit for %c found at %zu\n", c, uchar_bit_lookup(lookup, c));
    }
}

顺便说一句，这听起来像是微观优化。先完成你的解决方案（将所需操作抽象成这些函数），然后根据你的分析结果进行优化。如果你要专注于微观优化，请确保你的分析目标是你的解决方案将在其上运行的系统，因为即使硬件稍有不同，微观优化的效率也会有很大差异...通常更好的想法是购买一台更快的电脑 ;)

- autistic