c++ - 访问位域中的所有空闲插槽

我有一个uint64数组，对于所有未设置的位(0s)，我进行一些评估。

评估不是很昂贵，但是很少有未设置的位。分析说，我花了很多时间来寻找下一个未设置位的逻辑。

是否有更快的方法(在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的任何讨论都将是一个有趣的切线!)

最佳答案

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