c - 最低位索引

Question

我想找到最快的方法来获取 long long 的最低位的索引。即:

00101001001000 -> 3

涉及循环和移位的解决方案太慢了。即:

int i;
if(bits == 0ULL) {
  i = 64;
} else {
  for(i = 0;!(bits & 1ULL);i++)
    bits >>= 1;
}

编辑:使用信息

使用ffsll的函数并不能真正减少它的使用量，但是在这里(当然是简化了)。它只是遍历索引并对它们做一些事情。这个函数可能是我整个应用程序中使用最广泛的函数，尽管它的值有很多缓存。这是我的 alpha-beta 中的合法移动生成器搜索引擎。

while(bits){
  index = ffsll(bits);
  doSomething(index);
  index &= index-1;
}

Answer 1

英特尔有专门的指令来查找最低或最高阶设置位。 BSF看起来像你需要的。至于用纯 C 做，也许是 bit twiddling hacks page有你需要的。

至少您可以使用半字节或字节表来加快处理速度。类似这样的东西(针对 int 进行了演示，但可以根据需要轻松更改为 longlong)。

/*
0000 - 0
0001 - 1
0010 - 2
0011 - 1
0100 - 3
0101 - 1
0110 - 2
0111 - 1
1000 - 4
1001 - 1
1010 - 2
1011 - 1
1100 - 3
1101 - 1
1110 - 2
1111 - 1
*/

int ffs(int i) {
    int ret = 0;
    int j = 0;
    static const int _ffs_tab[] = 
        { 0, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 };

    while((i != 0) && (ret == 0)) {
        ret = _ffs_tab[i & 0x0f];

        if(ret > 0) {
            break;
        }

        i >>= 4;
        j += 4;

        /* technically the sign bit could stay, so we mask it out to be sure */
        i &= INT_MAX;
    }

    if(ret != 0) {
        ret += j;
    }

    return ret;
}