长整数中的单个位的索引(在C中)

Question

我试图找到一个最佳代码来定位长整数(64位)中的单个位索引.长整数只有一个设置位.(使用C语言)

目前,我只是将整个事情转移一点,然后检查零.我已经阅读了有关查找表的内容,但它不会对整个64位进行操作.我考虑过将每个8位检查为零,如果不使用查找,但我仍然需要一次移动8位.(换挡8比换挡8次要好？)

(注意:我正在为移动设备开发,它们[并不奇怪]慢).

Answer 1

每当我需要一些操作位的方法时,我总是寻找Bit Twiddling Hacks.它也没有解决您的问题的方法.

这个解决方案似乎很快且最先进:

将右侧的连续零位(尾随)并行计数

unsigned int v;      // 32-bit word input to count zero bits on right
unsigned int c = 32; // c will be the number of zero bits on the right
v &= -signed(v);
if (v) c--;
if (v & 0x0000FFFF) c -= 16;
if (v & 0x00FF00FF) c -= 8;
if (v & 0x0F0F0F0F) c -= 4;
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;

对于N位字,操作次数最多为3*lg(N)+ 4.

Answer 2

你可以对所设置的位进行二进制搜索:

int bitn(unsigned long long x)
{
    int n = 0;

    if (x >> 32) {
        n += 32;
        x >>= 32;
    }
    if (x >> 16) {
        n += 16;
        x >>= 16;
    }
    if (x >> 8) {
        n += 8;
        x >>= 8;
    }
    if (x >> 4) {
        n += 4;
        x >>= 4;
    }
    if (x >> 2) {
        n += 2;
        x >>= 2;
    }
    if (x >> 1) {
        n += 1;
    }

    return n;
}

GCC提供了一个内置的,__builtin_ctzll()它执行此功能(它将利用硬件可能具有的任何特殊功能来快速完成此操作).