最低阶位索引

英特尔有专门的指令来查找最低或最高阶的集合位。 BSF 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;
}

我发现最快的是 ffsll (long long) 在字符串中。

_BitScanForward :

• http://msdn.microsoft.com/en-us/library/wfd9z0bb(VS.80).aspx ( _BitScanForward )

__builtin_ctz __builtin_ffs

• http://developer.apple.com/mac/library/documentation/DeveloperTools/gcc-4.0.1/gcc/Other-Builtins.html (random gcc intrinsics documentation)

您可以使用 x & (~x + 1) ; 这将为您提供最低的位值,而不是索引(例如,如果x=01101000,则结果为000011000)。我所知道的从那里到索引的最快方法可能是switch语句:

switch(x & (~x + 1))
{
  case     0ULL: index = -1; break;
  case     1ULL: index =  0; break;
  case     2ULL: index =  1; break;
  case     4ULL: index =  2; break;
  ...
  case 9223372036854775808ULL: index = 63; break;
}

丑陋,但不涉及循环。

实现一种二进制搜索怎么样?

查看由位和掩码值产生的低位,掩码值都在低位。如果该值为零,则知道最小的位位于数字的上半部分。

另一个聪明人把这东西切成两半,然后再去。

这可能适用于32位。应该很容易扩展到64。

// all bits left of lsb become 1, lsb & right become 0
y = x ^ (-x);

// XOR a shifted copy recovers a single 1 in the lsb's location
u = y ^ (y >> 1);

// .. and isolate the bit in log2 of number of bits
i0 = (u & 0xAAAAAAAA) ?  1 : 0;
i1 = (u & 0xCCCCCCCC) ?  2 : 0;
i2 = (u & 0xF0F0F0F0) ?  4 : 0;
i3 = (u & 0xFF00FF00) ?  8 : 0;
i4 = (u & 0xFFFF0000) ? 16 : 0;
index = i4 | i3 | i2 | i1 | i0;

显然,如果有某种方法让硬件去做这件事,也就是说,如果有特殊的CPU指令可用,这就是方法。

像这样的怎么样?它大大减少了循环的数量。

int shifts = 0;
if ((bits & 0xFFFFFFFFFFFFULL) == 0) // not in bottom 48 bits
{
    shifts = 48;
}
else if ((bits & 0xFFFFFFFFFFULL == 0) // not in bottom 40 bits
{
    shifts = 40;
}
else
// etc

bits >>= shifts;  // do all the shifts at once

// this will loop at most 8 times
for(i = 0;!(bits & 1ULL);i++)
    bits >>= 1;

index = shifts + i;

我编写了两个函数,它们返回的结果与ffsll()相同。

int func1( uint64_t n ){
  if( n == 0 ) return 0;
  n ^= n-1;
  int i = 0;
  if( n >= 1ull<<32 ){ n>>=32; i+=32; }
  if( n >= 1ull<<16 ){ n>>=16; i+=16; }
  if( n >= 1ull<< 8 ){ n>>= 8; i+= 8; }
  if( n >= 1ull<< 4 ){ n>>= 4; i+= 4; }
  if( n >= 1ull<< 2 ){ n>>= 2; i+= 2; }
  if( n >= 1ull<< 1 ){         i+= 1; }
  return i+1;
}

int func2( uint64_t n ){
  return n? ((union ieee754_float)((float)(n^(n-1)))).ieee.exponent-126: 0;
}

unsigned int bsf_asm(unsigned int b)
{

    // b == 0 is undefined

#if defined( \__GNUC__ )

    return __builtin_ctz(b);

#else

    __asm bsf eax, b;

#endif

}


unsigned int bsf(unsigned int b)
{

    // b == 0 is undefined

    static const unsigned char btal[] = {0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0};

    int i = 0;
    if(!(b & 0x0000ffff))
    {
        b>>=16;
        i+=16;
    }

    if(!(b & 0x000000ff))
    {
        b>>=8;
        i+=8;
    }

    if(!(b & 0x0000000f))
    {
        b>>=4;
        i+=4;
    }

    return i+btal[b&0x0f];

}

考虑变量x

x&~(x-1)给出一个二进制数,该二进制数仅包含设置位,其余均为零

x      = 0101
x-1    = 0100
~(x-1) = 1011

x & ~ (x - 1) = 0100

现在继续向右移位这个二进制数,直到该数字为零,然后计算移位的次数,这将给出最右边的设置位数。

如果是偶数,则最低阶位为第一位。