最低位的索引

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中这样做,也许有点麻烦的黑客页面有你需要的.

至少你可以使用一个半字节或字节表来加快速度.像这样的东西(为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;
}

Answer 2

我找到的最快的是string.h.ffsll(long long)