## NVIDIA Agilent Technologies Interview Question

Software Engineer / DevelopersNot correct !!.

Take input V = 4 ( C should be 1 )

First pass:

V &= 3 => V = 3 , C = 1

Second Pass:

V &= 2 => V = 2, C = 2

so on... C will be 4

One more recursive method:

unsigned int bitCount( unsingned int data)

{

if(data & 1 == 1)

return (1 + bitCount(data>>=1));

else

return (bitCount(data>>=1));

}

unsigned int bitCount(unsingned int data)

{

int count=0;

while(data)

{

count++;

data = data & (data-1);

}

return count;

}

unsigned int BitCount( usigned int x)

{

x= ((x&0xAAAA)>>1)+(x&0x5555);

x= ((x&0xCCCC)>>2)+(x&0x3333);

x= ((x&0xF0F0)>>4)+(x&0x0F0F);

x= ((x&0xFF00)>>8)+(x&0x00FF);

}

unsigned int bitcount ( unsigned int x )

{

unsigned int max_count = sizeof(int),count = 0;

unsigned int base = 1;

while ( x & base && count <= max_count)

{

/* increase count , and shift base bit */

count++;

base << 1;

}

return count;

}

I won't write out the code (cuz I'm lazy) but I have a very different approach to this that would be much faster than the above methods - but there's definitely a memory trade off.

Preinitialize an array of length 256 bytes. Initialize each element of the array with the number of bytes for that index. For example:

array[0] = 0; // because '0' has 0 ON bits

array[1] = 1; // because '1' has 1 ON bit

array[2] = 1; // because '2' has 1 ON bit

array[3] = 2; // because '3' has 2 ON bits

...

array[255] = 8; // because '255' has 8 ON bits

Then take your 32 bit integer and break it into 4 8-bit pieces. Use each piece as an index into the above array. Add up the 4 values. Bam! You're done. You could also preinitialize an array of length 65536 and break your 32 bit integer into 2 16-bit pieces. Hell, you could preinitialize an array of length 4294967296 and just use the original number as an index into the array.

I had the same idea as John ( mentioned in an earlier post), and here's the code.

/* number of bits set to 1 for 0 - 15 */

int numBits = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};

int numBitsSet(unsigned x)

{

int ii = 0, mask = 0x000F;

for(ii = 0; ii < 4; ii++)

{

s = ii * 4; /* to shift mask by 4 bits each iteration */

count += numBits[(mask<<s) & x];

}

return count;

}

Isnt this a favorite question?

- Seshagiri February 05, 2006unsigned int v; // count the number of bits set in v

unsigned int c; // c accumulates the total bits set in v

for (c = 0; v; c++)

{

v &= v - 1; // clear the least significant bit set

}