Count number of bits in an unsigned integer

Question

I want to write a function named bitCount() in the file: bitcount.c that returns the number of bits in the binary representation of its unsigned integer argument.

Here is what I have so far:

#include <stdio.h>

int bitCount (unsigned int n);

int main () {
    printf ("# 1-bits in base 2 representation of %u = %d, should be 0\n",
        0, bitCount (0));
    printf ("# 1-bits in base 2 representation of %u = %d, should be 1\n",
        1, bitCount (1));
    printf ("# 1-bits in base 2 representation of %u = %d, should be 16\n",
        2863311530u, bitCount (2863311530u));
    printf ("# 1-bits in base 2 representation of %u = %d, should be 1\n",
        536870912, bitCount (536870912));
    printf ("# 1-bits in base 2 representation of %u = %d, should be 32\n",
        4294967295u, bitCount (4294967295u));
    return 0;
}

int bitCount (unsigned int n) {
    /* your code here */
}

Okay, when I just run this I get:

# 1-bits in base 2 representation of 0 = 1, should be 0
# 1-bits in base 2 representation of 1 = 56, should be 1
# 1-bits in base 2 representation of 2863311530 = 57, should be 16
# 1-bits in base 2 representation of 536870912 = 67, should be 1
# 1-bits in base 2 representation of 4294967295 = 65, should be 32

RUN SUCCESSFUL (total time: 14ms)

It doesn't return the correct numbers of bits.

What's the best way to return the number of bits in the binary representation of its unsigned integer argument in C?

Solution 1

 int bitCount(unsigned int n) {

    int counter = 0;
    while(n) {
        counter += n % 2;
        n >>= 1;
    }
    return counter;
 }

Solution 2

Here's a solution that doesn't need to iterate. It takes advantage of the fact that adding bits in binary is completely independent of the position of the bit and the sum is never more than 2 bits. 00+00=00, 00+01=01, 01+00=01, 01+01=10. The first addition adds 16 different 1-bit values simultaneously, the second adds 8 2-bit values, and each one after does half as many until there's only one value left.

int bitCount(unsigned int n)
{
    n = ((0xaaaaaaaa & n) >> 1) + (0x55555555 & n);
    n = ((0xcccccccc & n) >> 2) + (0x33333333 & n);
    n = ((0xf0f0f0f0 & n) >> 4) + (0x0f0f0f0f & n);
    n = ((0xff00ff00 & n) >> 8) + (0x00ff00ff & n);
    n = ((0xffff0000 & n) >> 16) + (0x0000ffff & n);
    return n;
}

This is hard-coded to 32 bit integers, if yours are a different size it will need adjusting.

Solution 3

Turns out there are some pretty sophisticated ways to compute this as answered here.

The following impl (I learned way back) simply loops knocking off the least significant bit on each iteration.

int bitCount(unsigned int n) {

  int counter = 0;
  while(n) {
    counter ++;
    n &= (n - 1);
  }
  return counter;
}

Comments

[ogzd]

what did you try in bitCount() ?

[Hot Licks]

I think you're missing "your code here".

[harold]

Would you be allowed to use __builtin_popcount?

[user2054534]

thank you, could you explain a bit more too? would be nice like i can cleaerly read your code, but I don't understand why it works

[ogzd]

According to the "-1", I should leave the understanding part to you as a practice

[user2054534]

i didn't downvote it it won't even let me vote "vote up requires 15 reputation" "vote down requires 125"

[Barmar]

Think about what each line does, it should become obvious. This is how you learn.

[user2054534]

i don't understand what n>>=1; does though any hint?

[Nikos C.]

@user2054534 n >>= 1 is the same as n = n >> 1.

[phuclv]

This method is naive and slow. There are many much faster algorithms to cound bit in this page

[chux - Reinstate Monica]

IMO, using % with / or & with >> is more consistent than % with >>. With n as unsigned, code can mix and match. Yet using arithmetic xor logical operators is less jarring to read.

[Pyjong]

I don't get it but holy Jeebus it just werks, so I'm going to put in the effort to understand this. Thanks!!

[Pyjong]

Ok now I get it, this is epic

[theonlygusti]

No the linked resource about the hamming weight is totally different. Hamming weight (0b10000) is 1 because only 1 bit is set. However bitCount(0b10000) is correctly 5

[Mark Ransom]

@theonlygusti did you even try this code? ideone.com/MEHIkC Each pass through the loop knocks out a 1 bit, completely ignoring the 0 bits.