0

If I have a int i = 15; I know it is 0x00 00 00 0F in binary is 0000 0000 0000 0000 0000 0000 0000 1111 has 4 1 in binary.

I want to count the sum of 1 in a int variable.

I write this:

int count1(int i)
{
    int j = 0,num = 0;
    for(;j<32;j++)
        if((i<<j )&0x80000000)
            num++;
    return num;
}

It can work, but I think it is too slow,I mean maybe I have millions int data. Dose some one have a more effective way to do this?

devnull
  • 118,548
  • 33
  • 236
  • 227
Lidong Guo
  • 2,817
  • 2
  • 19
  • 31

4 Answers4

2
int countSetBits(int n)
{
    unsigned int count = 0;
    while (n)
    {
      n &= (n-1) ;
      count++;
    }
    return count;
}

This method of counting the set bits in a number is called Brian Kernighan’s Algorithm, where the loop will iterate only upto the number of set bits. ie., in your case of example this will loop through 4 times only and need not loop the entire 32 times.

Opener
  • 145
  • 1
  • 8
1
int main() 
{ 

    int number = 15; 
    int sum; // total bits set in number
    for (sum = 0; number; sum++)
    {
      number &= number - 1; 
    }
    cout<<sum<<endl;
}
  • If it is faster ,can you explain why? – Lidong Guo Aug 20 '13 at 04:57
  • 1
    It uses less CPU instructions to calculate the number of SET bits. I read it in one link. Let me search that link for you. In that link, he has explained so many other ways to calculate number of set bits. But I found the above method easy. –  Aug 20 '13 at 05:05
  • 1
    I read the link and find this answer . – Lidong Guo Aug 20 '13 at 05:16
  • @LidongGuo this logic works faster because it need not loop through all the bits(for example no need of 32 iteration for a 4 byte variable), it can just loop through only set number of bits(ie., if 2 bits are set than just iterate 2 times only). But things will be different if all the bits of a variable is set, in this case any method will consume same execution. – Opener Aug 21 '13 at 11:31
0

This should work: 

int countOnes (int i) {

    int num = 0;
    while (i) {
        if (i % 2)
            num++;
        i = i >> 1;
    }

    return num;
}
verbose
  • 7,827
  • 1
  • 25
  • 40
0

You can simply keep on trimming the number. Let us assume that the binary number is stored in an int variable bin.

//This Function accepts binary value to count how many ones are there in it.

int count(int bin)
{
    int num=0;
    while(bin>=1)
    {
        if(bin%10 == 1)
        {
            num++;
        }
        bin=bin/10;
    }
    return num;
}
Kunal Khanna
  • 121
  • 2
  • 10