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

发布时间：2020-12-16 10:52:01 所属栏目：百科来源：网络整理

导读：我有一个uint64数组,对于所有未设置的位(0),我做了一些评估. 评估并不是非常昂贵,但很少有人没有设置.分析表明我花了很多时间在寻找下一个未设置位逻辑. 有没有更快的方法(在Core2duo上)？我当前的代码可以跳过很多高1： for(int y=0; yheight; y++) { uint

我有一个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的任何讨论,这将是一个有趣的切线！)

解决方法

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!