Counting number of 1's and 0's from integer with bitwise operation

Question

Is there a better way of doing this?

// Definition: Count number of 1's and 0's from integer with bitwise operation
//
// 2^32 = 4,294,967,296
// unsigned int 32 bit

#include<stdio.h>

int CountOnesFromInteger(unsigned int);

int main()
{
    unsigned int inputValue;
    short unsigned int onesOfValue;
    printf("Please Enter value (between 0 to 4,294,967,295) : ");
    scanf("%u",&inputValue);
    onesOfValue = CountOnesFromInteger(inputValue);

    printf("\nThe Number has \"%d\" 1's and \"%d\" 0's",onesOfValue,32-onesOfValue);
}

int CountOnesFromInteger(unsigned int value)
{
    unsigned short int i, count = 0;
    for(i = 0; i < 32 ; i++)
    {
        if (value % 2 != 0)
        {
            count++;
        }
        value = value >> 1;
    }
    return count;
}

Answer 1

Yes, there is a better way:

int CountOnesFromInteger(unsigned int value) {
    int count;
    for (count = 0; value != 0; count++, value &= value-1);
    return count;
}

The code relies on the fact that the expression x &= x-1; removes the rightmost bit from x that is set. We keep doing so until no more 1's are removed. This technique is described in K&R.

This approach is superior because it doesn't depend on an integer's size - it's totally portable - and it tests every bit in a fairly efficient way (with the comparison value != 0).

Also, you might want to replace 32 in main() with sizeof(int)*CHAR_BIT so that your code doesn't depend on an integer using 32 bits:

#include <stdio.h>
#include <limits.h>

int CountOnesFromInteger(unsigned int);

int main()
{
    unsigned int inputValue;
    short unsigned int onesOfValue;
    printf("Please Enter value (between 0 to 4,294,967,295) : ");
    scanf("%u",&inputValue);
    onesOfValue = CountOnesFromInteger(inputValue);

    printf("\nThe Number has \"%d\" 1's and \"%zu\" 0's",onesOfValue,sizeof(int)*CHAR_BIT-onesOfValue);
    return 0;
}

Answer 2

I'd go for a non standard function, because C sucks with bit operations:

#include <stdio.h>

#ifdef __GNUC__
int popcount(int x) {
  return __builtin_popcount(x);
}
#else
#error Unimplemented popcount
#endif


int main(void)
{
  int x;
  scanf("%d", &x);

  printf("%d\n", popcount(x));

  return 0;
}

This will be translated to efficient processor instructions where available, or an efficient library implementation where it's not.

References: http://en.wikipedia.org/wiki/Hamming_weight

https://stackoverflow.com/questions/15736602/fastest-way-to-count-number-of-1s-in-a-register-arm-assembly

http://wm.ite.pl/articles/sse-popcount.html

http://gcc.gnu.org/onlinedocs/gcc-4.8.2/gcc/Other-Builtins.html#Other-Builtins

Answer 3

From a StackOverflow answer:

int CountOnesFromInteger(uint32_t i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

This is the best known implementation for the general case. The explanation (see popcount_3) is that it works with groups of 2, 4, and 8 bits.

The solution posted by @FilipeGonçalves is best for sparse bitsets.

Answer 4

@Filipe hit the main point I wanted to cover. But there are some minor improvements that can be made.

---

Remove the != 0 for maximum C-ness.

if (value % 2)

---

If you are not taking any parameters into main(), you should declare them void.

int main(void)

---

You don't have any return statement, yet you declare that you are returning an int. Let's return 0 at the end of our program to indicate success.

return 0;