访问位域中的所有空闲位置

Question

我有一个uint64数组,对于所有未设置的位(0),我做了一些评估.

评估并不是非常昂贵,但很少有人没有设置.分析表明我花了很多时间在寻找下一个未设置位逻辑.

有没有更快的方法(在Core2duo上)？

我当前的代码可以跳过很多高1:

for(int y=0; y<height; y++) {
  uint64_t xbits = ~board[y];
  int x = 0;
  while(xbits) {
    if(xbits & 1) {
      ... with x and y
    }
    x++;
    xbits >>= 1;
  }
}

(以及关于如何/如果SIMD/CUDA的任何讨论,这将是一个有趣的切线!)

Answer 1

Hacker's Delight建议使用循环展开的二进制搜索.不漂亮,但对于稀疏的未设置位快,因为它跳过dwords/bytes/nibbles/etc. 每一位都设置好.

如果你能得到一个带有SSE4a的Phenom(不幸的是不是Core2 Duo),你可以使用POPCNT来编写一个快速的设置位数功能.然后你可以得到下一个未设置位的索引:

pop(x & (~x-1))

x & (~x-1)清除下一个零位上方的设置位; 然后你只需用POPCNT计算剩余的位数.

这是一个带有字节的工作示例:

    01101111 x
    10010000 ~x
    10001111 ~x-1
    00001111 x & ~x-1
pop(00001111) => 4