NVIDIA Interview Question Software Engineer / Developers
the idea is correct, just extend it for 32-bit ints:
assume bitcount stores # of 1's set in 1 byte:
unsigned nbits(unsigned x)
{
unsigned char cnt = 0;
cnt += bitcount[ x & 0xff ]; x >>= 8;
cnt += bitcount[ x & 0xff ]; x >>= 8;
cnt += bitcount[ x & 0xff ]; x >>= 8;
cnt += bitcount[ x ];
return cnt;
}
however counting the number of operations + additional space for table this might be not optimal, other solution:
nbits(x) {
x = ((x>>1) & 0x55555555UL) + (x & 0x55555555UL);
x = ((x>>2) & 0x33333333UL) + (x & 0x33333333UL);
x = ((x>>4) + x) & 0x0f0f0f0fUL; // 0-8 in 4 bits
x += x>> 8; // 0-16 in 8 bits
x += x>>16; // 0-32 in 8 bits
return x & 0xff;
}
i think the question is about finding number of bit set to 1 in a binary representation of a given number.
sol :
cnt =0;
while(n)
{
n &= (n-1); // set left most 1's to 0
cnt++;
}
cout<< "number of 1's : " << cnt;
i think the question is about finding number of bit set to 1 in a binary representation of a given number.
sol :
cnt =0;
while(n)
{
n &= (n-1); // set left most 1's to 0
cnt++;
}
cout<< "number of 1's : " << cnt;
bit hacking is way faster. This is for 16bit integer.
- tc September 05, 2008int table[] = {0,1,1,2,1,2,2,3, 1,2,2,3,2,3,3,4}
#define f(x) table[x&(0xf)]
int count(int num){
return f(num) + f(num>>4) + f(num>>8) + f(num>>16);
}