c++ - 计算连续 1 位的最快方法。 C++

Question

基本上我只需要知道 int 或 unsigned int 中最高 1 位的位置。喜欢:

00001111=4;
00011111=5;
11111111=8;

因为我确信我得到的任何数字都会有连续的 1 位。 0...0000011...1 不会有 ..00010011... 之类的。所以方法可以找到最高的 1 或者只计算 1s。不管。

这是我设法做到的最好的:

Uint32 number;
int shift=16; int segment=8;
while (segment) 
{
if (number>>shift!=0) shift+=segment; 
else shift-=segment;
segment>>1; // /2
}

Answer 1

为它复制/粘贴我的函数:

size_t FirstSetBit(unsigned int v) const
{
#if defined(_MSC_VER)
    unsigned long ul;
    // Just 10% faster than MultiplyDeBruijnBitPosition method, on Core i7
    _BitScanForward(&ul, v);
    return ul;
#elif defined(__GNUC__) || defined(__clang__)
    return 31 - __builtin_clz(v);
#else // integer fallback for non-x64
    #warning You may be able to optimise this code for your compiler/processor

    int r;
    static const int MultiplyDeBruijnBitPosition[32] =
    {
        0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
    };

    r = MultiplyDeBruijnBitPosition[(uint32_t((v & -int(v)) * 0x077CB531U)) >> 27];
return r;
#endif
}