c++ - 以十进制数的二进制格式计算 1 的个数

Question

我想找出一个大十进制数(十进制数可以大到 1000000)的二进制形式的 1 的个数。

我试过这段代码:

while(sum>0)  
{  
    if(sum%2 != 0)  
    {  
        c++;   // counting number of ones  
    }  
    sum=sum/2;  
}  

我想要一个更快的算法，因为它需要很长时间才能输入大量小数。请建议我一个有效的算法。

Answer 1

您正在寻找的是“popcount”，它在后来的 x64 CPU 上作为单个 CPU 指令实现，速度不会被打败:

#ifdef __APPLE__
#define NAME(name) _##name
#else
#define NAME(name) name
#endif

/*
 * Count the number of bits set in the bitboard.
 *
 * %rdi: bb
 */
.globl NAME(cpuPopcount);
NAME(cpuPopcount):
    popcnt %rdi, %rax
    ret

当然，您需要先测试 CPU 是否支持它:

/*
 * Test if the CPU has the popcnt instruction.
 */
.globl NAME(cpuHasPopcount);
NAME(cpuHasPopcount):
    pushq %rbx

    movl $1, %eax
    cpuid                   // ecx=feature info 1, edx=feature info 2

    xorl %eax, %eax

    testl $1 << 23, %ecx
    jz 1f
    movl $1, %eax

1:
    popq %rbx
    ret

下面是 C 语言的实现:

unsigned cppPopcount(unsigned bb)
{
#define C55 0x5555555555555555ULL
#define C33 0x3333333333333333ULL
#define C0F 0x0f0f0f0f0f0f0f0fULL
#define C01 0x0101010101010101ULL

    bb -= (bb >> 1) & C55;              // put count of each 2 bits into those 2 bits
    bb = (bb & C33) + ((bb >> 2) & C33);// put count of each 4 bits into those 4 bits
    bb = (bb + (bb >> 4)) & C0F;        // put count of each 8 bits into those 8 bits
    return (bb * C01) >> 56;            // returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...
}

GNU C 编译器运行时包含一个“内置”，它可能比上面的实现更快(它可能使用 CPU popcnt 指令，但这是特定于实现的):

unsigned builtinPopcount(unsigned bb)
{
    return __builtin_popcountll(bb);
}

我的 C++ 国际象棋库中使用了上述所有实现，因为当位板用于表示棋子位置时，popcount 在国际象棋移动生成中起着至关重要的作用。我使用在库初始化期间设置的函数指针指向用户请求的实现，然后通过该指针使用 popcount 函数。

Google 将提供许多其他实现，因为这是一个有趣的问题，例如:http://wiki.cs.pdx.edu/forge/popcount.html .