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

概述我有一个uint64数组,对于所有未设置的位(0),我做了一些评估. 评估并不是非常昂贵,但很少有人没有设置.分析表明我花了很多时间在寻找下一个未设置位逻辑. 有没有更快的方法(在Core2duo上)？ 我当前的代码可以跳过很多高1： for(int y=0; y<height; y++) { uint64_t xbits = ~board[y]; int x = 0; while(x 我有一个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-1pop(00001111) => 4

总结

以上是内存溢出为你收集整理的c – 访问位域中的所有空闲插槽全部内容，希望文章能够帮你解决c – 访问位域中的所有空闲插槽所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。