## NVIDIA Interview Question

Software Engineer / Developersthe 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);

}