Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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

4 Answers 4

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;
}
share|improve this answer
1  
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 Dec 27 '13 at 22:40
1  
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. –  Frerich Raabe Dec 27 '13 at 22:45
    
@FrerichRaabe Thanks for noting that. I edited my answer. –  Filipe Gonçalves Dec 28 '13 at 12:05
add comment

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

http://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

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

@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;
share|improve this answer
1  
I believe main should also return something (return 0; is only implicit for C++ IIRC). –  Frerich Raabe Dec 27 '13 at 22:41
    
@FrerichRaabe Good catch, I've edited that it. –  syb0rg Dec 27 '13 at 22:43
add comment

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.

share|improve this answer
    
Yes! To the interested reader there's a whole chapter on this in Hacker's Delight by Warren. –  NeuroFuzzy Jan 3 at 7:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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