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

• Michael Urman: Considering the title's reference to a bitwise operator, I was surprised to see if (value % 2 != 0) instead of if (value & 1).

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

• Frerich Raabe: I think and it doesn't have to test every bit isn't really the truth (it's impossible to solve this problem without testing all bits); the value != 0 expression is just a fairly efficient way to test all bits (by doing so in parallel).
• Frerich Raabe: Also the loop will run in time proportional to the number of ones sounds imprecise as well - the number of iterations of the loop doesn't depend on the number of ones, it merely depends on the position of the most significant one.
• Filipe Gonçalves: @FrerichRaabe Thanks for noting that. I edited my answer.

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

• 200_success: Why do you say that C sucks with bit operations?
• 200_success: For compatibility, I would define int CountOnesfromInteger(unsigned int value) { #ifdef __GNUC__ return __builtin_popcount(value); #else /* Your own implementation */ #endif }`.

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.

• user34350: Yes! To the interested reader there's a whole chapter on this in Hacker's Delight by Warren.

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;

• Frerich Raabe: I believe main should also return something (return 0; is only implicit for C++ IIRC).
• syb0rg: @FrerichRaabe Good catch, I've edited that it.
• Edward: @FrerichRaabe: Starting with the C99 standard, the compiler is required to generate the equivalent of a return 0 or return EXIT_SUCCESS if no return is supplied at the end of main.