统计十进制数的二进制格式中1的个数

Question

我正在尝试找出一个大的十进制数（十进制数可以达到1000000）的二进制形式中1的数量。

我尝试了这段代码：

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

我希望能有一个更快的算法，因为对于大量小数输入来说，时间太长了。请给我推荐一个高效的算法。

- zalenix

---

1000000并不是很大的数。为什么不将其转换为字符串并计算其中的数字1呢？ - Rapptz

真的吗？20次迭代需要很长时间吗？ - chris

@Rapptz，我希望你的意思是不要重复造轮子，而是使用std::count :) - chris

这是一个汉明权重问题：http://en.wikipedia.org/wiki/Hamming_weight。阅读一下，你可能会对如何滥用二进制运算符有所启发 :-) - Najzero

这里有几个很酷的简单算法，可以快速计算位数。根据不同的情况，其中一些算法比其他算法更好。 - thang

这段代码很快，它按log(n)的顺序执行，不过我建议用c += (sum&1)作为微小的增强，因为模运算与“and”操作相反需要一些时间; 而且你也可以使用右移代替除法，这样就变成了(sum >>= 1)，但我猜这不是你想要的。 - Amr Saber

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指令，但这取决于具体实现）：

GNU C编译器运行时包含一个“内置函数”，可能比上面的实现更快（它可能使用CPU的popcnt指令，但这取决于具体实现）：

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

在我的C++棋类库中，所有上述实现都用于popcount，在使用位板表示棋子位置时生成棋步是至关重要的。我使用函数指针，在库初始化期间设置它以指向用户请求的实现，然后通过该指针使用popcount函数。

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

- trojanfoe

Answer 2

在 C++ 中，您只需这样做。

#include <bitset>
#include <iostream>
#include <climits>

size_t popcount(size_t n) {
    std::bitset<sizeof(size_t) * CHAR_BIT> b(n);
    return b.count();
}

int main() {
    std::cout << popcount(1000000);
}

- Rapptz

---

为什么假设是32位？size_t不一定是32位。而且1字节不一定意味着8位。因此，我修改了答案。 - Nawaz

@Nawaz的回答说“高达100万”，所以我认为32位就足够了。不过我很感谢你的编辑。 - Rapptz

哦，嘿，我实际上是在进行 C++ 谷歌搜索之后偶然发现了这个答案。嗨, 丹尼！ - user6516765

有想法如何将其作为constexpr吗？ - EgoPingvina

Answer 3

有许多方法。易于理解且相当快速的方法是Brian Kernighan的方法：

unsigned int v = value(); // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

- BЈовић

---

我点赞了这个，因为它非常漂亮整洁。尽管比大多数popcount实现需要更多的迭代次数 :-) - Najzero

我不明白，请解释一下这段代码：for (c = 0; v; c++)。变量 v 没有初始化。 - Nawaz

@Nawaz：从第一行的注释中可以判断，v应该包含我们想要计数位的值。 - Mike Seymour

@MikeSeymour：哦，谢谢。我编辑了答案，使它更好一些。 - Nawaz

@Nawaz 谢谢。我以为一个注释就足够了 :) - BЈовић

Answer 4

使用右移位运算符

    int number = 15; // this is input number
    int oneCount = number & 1 ? 1 : 0;
    while(number = number >> 1)
    {
        if(number & 1)
            ++oneCount;
    }

    cout << "# of ones :"<< oneCount << endl;

- Santosh Chauhan

---

如果数字是负数会发生什么？ - jrok

Answer 5

int count_1s_in_Num(int num)
{
    int count=0;
    while(num!=0)
    {
        num = num & (num-1);
        count++;
    }
    return count;
}

如果您将AND操作应用于整数和减法的结果，则结果是一个新数字，该数字与原始整数相同，只是最右边的1现在变成了0。例如，01110000 AND（01110000-1）= 01110000 AND 01101111 = 01100000。

此解决方案的运行时间为O（m），其中m是解决方案中1的数量。

- Praks