找出特定整数有多少二进制数字

Question

可能重复:
计算快速日志基数2上限

在C/C++中将特定整数从十进制转换为二进制时,找出特定整数有多少二进制数字的最快方法是什么？

防爆.47 ₍₁₀₎ = 101111 ₍₂₎

因此47有六位数以二进制表示.

Answer 1

要想快速有趣地执行此操作而无需调用数学函数,请检查以下内容:

for (digits = 0; val > 0; val >>= 1)
        digits++;

作为奖励,这应该煮至内存负载和2个使用中的寄存器,以获得额外的惊人效果.

Answer 2

如果您在性能方面寻找"最快"的方式,则需要采用特定于平台的方法.

有些架构实际上有一个指令可以做到这一点.

在x86上,您有bsr说明.

在MSVC中,它可以访问:

inline int bitlength(unsigned long x){
    if (x == 0)
        return 0;

    unsigned long index;
    _BitScanReverse(&index,x);
    return (int)(index + 1);
}

海湾合作委员会有__builtin_clz()内在的 - 它做了类似的事情.

Answer 3

多数民众赞成在提出最快的解决方法我最喜欢的一点摆弄黑客的集合是用乘法和查找查找为O N位整数的日志基地2(LG(N))操作.它需要13条指令才能找到数字中的最高设置位.

uint32_t v; // find the log base 2 of 32-bit v
int r;      // result goes here

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

v |= v >> 1; // first round down to one less than a power of 2 
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];