## NVIDIA Agilent Technologies Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
1
of 1 vote

Isnt this a favorite question?

unsigned 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
}

Comment hidden because of low score. Click to expand.
0

Not 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

Comment hidden because of low score. Click to expand.
0

4 & 3 = 0, not 3

Comment hidden because of low score. Click to expand.
0

It does not work for :
Assume initially v=40. It has only two bits
set ( 2^5 + 2^3 )...

Comment hidden because of low score. Click to expand.
0

why is there so many discussion with such a simple question?
This solution is definitely most effiecient and concise.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Excellent link showing different ways of solving the problem

http://www-db.stanford.edu/~manku/bitcount/bitcount.html

Comment hidden because of low score. Click to expand.
0
of 0 vote

One more recursive method:

unsigned int bitCount( unsingned int data)
{
if(data & 1 == 1)
return (1 + bitCount(data>>=1));
else
return (bitCount(data>>=1));
}

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

Two issues
1. Where does this recursion terminate??
2. Even if you add a recursion terminator, this program checks each bit...

The first solution is much more efficient

Comment hidden because of low score. Click to expand.
0
of 0 vote

unsigned int bitCount(unsingned int data)
{
int count=0;
while(data)
{
count++;
data = data & (data-1);
}
return count;
}

Comment hidden because of low score. Click to expand.
0

same as before just replaced for with while

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

}

Comment hidden because of low score. Click to expand.
0

correct, but for 32-bit int you need extended masks,
that is:

...
x = ((x >> 4) + x) & 0x0f0f0f0f;
x += x >> 8;
x += x >> 16;
return x & 0xff;

Comment hidden because of low score. Click to expand.
0
of 0 vote

in above program, 'return x;' is missing.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0

Look in Programming interviews Exposed book Page number 145

Comment hidden because of low score. Click to expand.
0
of 0 vote

int bitcount(unsigned int x)
{
int num = 0;

while (x)
{
if (x & 1 == 1) or x = x&(x-1);
{ num++; num++;
}
x = x>>1;
}
return num;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

How abt using quicksort and incrementing static variable if there is swap between two bits..time complexity will be lesser!!

Comment hidden because of low score. Click to expand.
0
of 0 vote

?

Comment hidden because of low score. Click to expand.
0
of 0 vote

private static count = 0;
public int CountOnIntegers(int someInteger)
{

while (someInteger != 0)
{
if ((someInteger & 1) == 1)
count++;
someInteger = someInteger >> 1;
}

return count;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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; // because '0' has 0 ON bits
array = 1; // because '1' has 1 ON bit
array = 1; // because '2' has 1 ON bit
array = 2; // because '3' has 2 ON bits
...
array = 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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

unsigned int numberOfOnBit(int n)
{
if(n == 0)
return 0;
unsigned c = 0;
while(n != 1)
{
n = n >> 1;
c++;
}
return c;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Xuka,

which bit ar you checking? And when does 'n' will be 1. ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

int no_of_onbit(int val)
{
while(val)
{
val = val & (val-1);
count++;
}

return count;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````short count_on_bits(int number)
{
short count = 0;
short bit_count = 0;
while(sizeof(int)*8 > bit_count) {
if(number & 1) {
count++;
}
number >>= 1;
bit_count++;
}
return count;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

int bitcount(unsigned x)
{
int b;
for (b = 0; x != 0; x >>= 1)
if (x & 01)
b++;
return b;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 */
}

return count;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

What most of the algorithms here is doing is counting the number of on bits which is undoubtedly trivial.. The actual question was how can u tell the no. of ON bits in a number without counting..

Comment hidden because of low score. Click to expand.
0
of 0 vote

int count_ones(int num) {
int count = 0;
while(num) {
count++;
num = num & (num-1);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int numOnBits(int num){

int count =0;
while(num>0){
if(num ^ ((num>>1)<<1))
count++;
num = num>>1;
}

return count;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
main()
{ int i,j,n,s=0;
printf("Enter the input\n");
scanf("%d",&n);
while(n>0)
{ if(n&1==1)
s++;
n=n>>1;
}
printf("The no of ON bits are %d\n",s);
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.