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

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

• Considering the title's reference to a bitwise operator, I was surprised to see if (value % 2 != 0) instead of if (value & 1). Dec 27, 2013 at 21:50

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

• 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). Dec 27, 2013 at 22:40
• 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. Dec 27, 2013 at 22:45
• @FrerichRaabe Thanks for noting that. I edited my answer. Dec 28, 2013 at 12:05

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

• Why do you say that C sucks with bit operations? Dec 28, 2013 at 17:59
• For compatibility, I would define int CountOnesfromInteger(unsigned int value) { #ifdef __GNUC__ return __builtin_popcount(value); #else /* Your own implementation */ #endif }. Dec 28, 2013 at 18:01

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.

• Yes! To the interested reader there's a whole chapter on this in Hacker's Delight by Warren.
– user34350
Jan 3, 2014 at 7:34

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

• I believe main should also return something (return 0; is only implicit for C++ IIRC). Dec 27, 2013 at 22:41
• @FrerichRaabe Good catch, I've edited that it. Dec 27, 2013 at 22:43
• @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`. Aug 20, 2015 at 16:16