CareerCup

Erm, kinda wrong answer I guess or I cant get it at least. best way to count set bits is do

while(number)
{number &= (number-1); count++;}

You clear one least significant 1 in binary representation of number on each iteration.

look at the second solution in the link,

puddleofriddles.blogspot.com/2012/03/count-bits-in-integer.html

Yeah right answer will be

while (v&=(v-1))
{
count++;
}

use divide and conquor approach
divide the 32 bit data into 8 bits(or less) and make a LookUpTable with 256 entries corresponding to each 8bit combination. For example

for an 8 bit num, we have 0-255 i.e 256 values;
now let us say that we have an array whose index contains number of 1s for that index(unsigned 8bit)
NumberOf1sAtIndex[]={0,1,1,2,1,2,......., 8};//

so we have 32 bit number right;
we can get number of 1s in a 32 bit number (create a copy of it and call it as num) by following :
for(i=0; i<32/8; i++) {
result+=NumberOf1sAtIndex[(unsigned) (num&0x00FF)];
num>>0x00FF;
}

Thus you can optimize the code depending upon:
(1) extract 4 bits and look up array NumberOf1sAtIndex will be reduce to size 16 rather than 256
(2) if your num will usually contain many zeros compared to 1s, then determine minimum how many zeros are there. Let us say that in each 8 bits there will be 4 or more zeros, then we will have max number 0xF0, then in that case, your NumberOf1sAtIndex size will become 256-2^4. Slight space compaction but significant sometimes

you can do this very fast on ARM with CLZ instruction. On linux that instruction is used to implement __ffs(), so we could:

u32 bitmap = INITIALIZE_SOMETHING_HERE;
u32 count = 0;

while (bitmap) {
unsigned long bit = __ffs(bitmap);

bitmap &= ~(1 << bit);
count++;
}

All of these answers modify the variable being tested. You generally don't want to do that.

Here's a version:

int i = 0;
    int count = 0;
    int num = 0x4a35;

    for (i = 0; i < BIT_COUNT; i++)
        if (num & (1 << i))
            count++;

int y;
cin>>y;
int count=0;
while(y)
{
if(y&1)
count++;
y>>=1;
}
cout<<count;

The best solution for sparse words has been covered (by Giorgi), but here's another more general population function from Hacker's Delight:

int pop( unsigned x )
{
   x = x - ((x >> 1) & 0x55555555);
   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
   x = (x + (x >> 4)) & 0x0F0F0F0F;
   x = x + (x >> 8);
   x = x + (x >> 16);
   return x & 0x0000003F;
}

It works without looping by using a divide and conquer strategy to sum bits from each adjacent bit-pair, nybble, byte, etc.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int count = 0;
	int num = 45; // say given number
	while(num){
		num = num & (num-1);
		count++;
	}
	cout << count << endl;
	return 0;
}

The algorithm to solve the above problem is to keep doing the check of `if(n&1 == 1)` is this is true increment the counter variable till the number is greater than 0 and at last return the counter variable to get the total number of 1s in the binary representation:

Implementation:

int countbits(int n){
    int count = 0;
    while(n > 0){
        if(n&1 == 1)
            count++;
        n = n>>1;
    }
    return count;
}
using namespace std;
int main(){
    int t, n;
    cin>>t;
    while(t--){
        cin>>n;
        cout<<countbits(n)<<endl;
    }
	return 0;

}