以最快的方式计数连续的1位。 C ++ [英] Fastest way to count consecutive 1 bits. C++

问题描述

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

Basicly I just need to know the position of the highest 1 bit inside of an int or unsigned int. Like:

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

因为我相信我得到的任何数字都将有连续的1位。 0 ... 0000011 ... 1没有..00010011 ...或者什么。所以方法可以找到最高的1或只计数1s。不管。

Because I am sure that any number I will get will have consecutive 1 bits. 0...0000011...1 There will be no ..00010011... or something. So method can find the highest 1 or just count 1s. No matter.

这是我最好做的事情：

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

推荐答案

粘贴我的函数为它：

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
}

这篇关于以最快的方式计数连续的1位。 C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！