26
\$\begingroup\$

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;
}
\$\endgroup\$
  • 3
    \$\begingroup\$ Considering the title's reference to a bitwise operator, I was surprised to see if (value % 2 != 0) instead of if (value & 1). \$\endgroup\$ – Michael Urman Dec 27 '13 at 21:50
27
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – Frerich Raabe Dec 27 '13 at 22:40
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Frerich Raabe Dec 27 '13 at 22:45
  • \$\begingroup\$ @FrerichRaabe Thanks for noting that. I edited my answer. \$\endgroup\$ – Filipe Gonçalves Dec 28 '13 at 12:05
6
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Why do you say that C sucks with bit operations? \$\endgroup\$ – 200_success Dec 28 '13 at 17:59
  • 1
    \$\begingroup\$ For compatibility, I would define int CountOnesfromInteger(unsigned int value) { #ifdef __GNUC__ return __builtin_popcount(value); #else /* Your own implementation */ #endif }`. \$\endgroup\$ – 200_success Dec 28 '13 at 18:01
6
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Yes! To the interested reader there's a whole chapter on this in Hacker's Delight by Warren. \$\endgroup\$ – user34350 Jan 3 '14 at 7:34
5
\$\begingroup\$

@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;
\$\endgroup\$
  • 1
    \$\begingroup\$ I believe main should also return something (return 0; is only implicit for C++ IIRC). \$\endgroup\$ – Frerich Raabe Dec 27 '13 at 22:41
  • \$\begingroup\$ @FrerichRaabe Good catch, I've edited that it. \$\endgroup\$ – syb0rg Dec 27 '13 at 22:43
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Edward Aug 20 '15 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.