C++ 以十进制数的二进制格式计算 1 的个数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/14682641/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Count number of 1's in binary format of decimal number
提问by zalenix
I am trying to find out the number of 1's in binary form of a large decimal number (decimal number can be as large as 1000000).
我试图找出一个大十进制数的二进制形式的 1 的数量（十进制数可以大到 1000000）。
I tried this piece of code:
我试过这段代码：
while(sum>0)
{
if(sum%2 != 0)
{
c++; // counting number of ones
}
sum=sum/2;
}
I want a faster algorithm as it takes long time for large decimal input. Please suggest me an efficient algorithm.
我想要一个更快的算法，因为大十进制输入需要很长时间。请建议我一个有效的算法。
回答by trojanfoe
What you are looking for is "popcount", which is implemented as a single CPU instruction on later x64 CPU's, which won't be beaten for speed:
您正在寻找的是“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
But of course, you'll need to test the CPU supports it first:
但是当然，您需要先测试 CPU 是否支持它：
/*
* Test if the CPU has the popcnt instruction.
*/
.globl NAME(cpuHasPopcount);
NAME(cpuHasPopcount):
pushq %rbx
movl , %eax
cpuid // ecx=feature info 1, edx=feature info 2
xorl %eax, %eax
testl << 23, %ecx
jz 1f
movl , %eax
1:
popq %rbx
ret
Here's an implementation in C:
这是 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) + ...
}
The GNU C Compiler runtime contains a "built-in" which might be faster than the implementation above (it might use the CPU popcnt instruction, but that's implementation-specific):
GNU C 编译器运行时包含一个“内置”，它可能比上面的实现更快（它可能使用 CPU popcnt 指令，但这是特定于实现的）：
unsigned builtinPopcount(unsigned bb)
{
return __builtin_popcountll(bb);
}
All of the above implementations are used in my C++ chess library as popcount plays a vital role in chess move generation when bitboards are used to represent piece positions. I use a function pointer, set-up during library initialisation, to point to the implementation requested by the user and then use the popcount function via that pointer.
所有上述实现都在我的 C++ 国际象棋库中使用，因为当使用位板表示棋子位置时，popcount 在国际象棋移动生成中起着至关重要的作用。我使用函数指针，在库初始化期间设置，指向用户请求的实现，然后通过该指针使用 popcount 函数。
Google will provide many other implementations as it's an interesting problem, for example: http://wiki.cs.pdx.edu/forge/popcount.html.
Google 将提供许多其他实现，因为这是一个有趣的问题，例如：http: //wiki.cs.pdx.edu/forge/popcount.html。
回答by Rapptz
In C++ you can just do this.
在 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);
}
回答by B?ови?
There are many ways. Easy to understand and quite fast is Brian Kernighan's way:
有很多方法。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
}
回答by Santosh Chauhan
using right bit shift operator
使用右位移运算符
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;
回答by Praks
int count_1s_in_Num(int num)
{
int count=0;
while(num!=0)
{
num = num & (num-1);
count++;
}
return count;
}
If you apply the AND operation to the integer and the result of the subtraction, the result is a new number that is the same as the original integer except that the rightmost 1 is now a 0. For example,01110000 AND (01110000 – 1) = 01110000 AND 01101111 = 01100000.
如果对整数和减法结果应用 AND 运算，结果是一个与原始整数相同的新数字，只是最右边的 1 现在是 0。例如，01110000 AND (01110000 – 1) = 01110000 和 01101111 = 01100000。
This solution has a running time of O(m), where m is the number of 1s in the solution.
该解决方案的运行时间为 O(m)，其中 m 是解决方案中 1 的数量。
