NVIDIA Interview Question
Software Engineer / Developersuse 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
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.
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;
}
Erm, kinda wrong answer I guess or I cant get it at least. best way to count set bits is do
You clear one least significant 1 in binary representation of number on each iteration.
- Giorgi March 16, 2011