Count number of 1's in binary format of decimal number

Question

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).

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.

Solution 1

In C++ you can just do this.

#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);
}

Solution 2

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:

#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:

/*
 * 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

Here's an implementation in 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):

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.

Google will provide many other implementations as it's an interesting problem, for example: http://wiki.cs.pdx.edu/forge/popcount.html.

Solution 3

There are many ways. Easy to understand and quite fast is Brian Kernighan's way :

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
}

Solution 4

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;

Solution 5

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.

This solution has a running time of O(m), where m is the number of 1s in the solution.

View more solutions

Comments

[Najzero]

upvoted this, because its so nice and tidy. Still takes more iterations than most popcount implementations :-)

[Nawaz]

Why assume 32 bit? size_t is not necessarily 32 bit. And 1 byte doesn't necessarily mean 8 bit. Therefore, I edited the answer.

[Rapptz]

@Nawaz Answer said "as large as 1 million" so I just figured 32-bits would be enough. I appreciate the edit though.

[Nawaz]

I dont get it. Explain this to me : for (c = 0; v; c++). v is uninitialized.

[Mike Seymour]

@Nawaz: Judging from the comment in the first line, v is supposed to contain the value whose bits we want to count.

[Nawaz]

@MikeSeymour: Oh. Thanks. I edited the answer to make it a bit better.

[BЈовић]

@Nawaz Thanks. I thought a comment would be enough :)

[jrok]

What happens if number is negative?

[Admin]

Oh hey, I actually stumbled upon this answer after a C++ google search. Hi Danny!

[EgoPingvina]

has an idea how to do it as constexpr?