# Thread: Please Explain Count the number of bits in an int code

1. ## Please Explain Count the number of bits in an int code

I am studying for an interview and I came across an interview that asks to count the number of bits in an int. I have the solution but I do not uderstand either solution. Woul somebody please explain it to me? Thanks

Code:
```int bitcount(int v)
{
for(int count=0; v; count++, v &= ~(v-1));
return count;

}

int table[] = {0,1,1,2,1,2,2,3, 1,2,2,3,2,3,3,4 };
#define bc(x) table[(x)&0xf ]   // maps nibbles to number of bits

int bitcount(int v)
{
// assume 16 bit int
return  bc(x) + bc(x>>4) + bc(x>>8) + bc(x>>12);

}```

2. shouldn't the 'x' be defined somewhere?

3. The second one is easy - it just determines number of bits in every 4-bit pattern
from 0 to 0xf (using table array)
Then calculate sum for each 4 bit pattern in the number (there are 4 in the 16-bit int)

the first one I cannot undertand

if v = 1

v &= ~(v-1)
is also 1
so it seems to me there is and endless loop there

PS. if that statement will be changed to
v &= (v-1)

it will remove one 1-bit from the number
so the loop counts number of bits in the number...
(havn't check it for negative numbers...

4. > I have the solution but I do not uderstand either solution
You have "a" solution.
One which requires a fair amount of knowledge about bits.

Could you write the code using the obvious for loop and bit test approach or not?

> I am studying for an interview
Unlike exams, which you can study for and largely forget, interviews for jobs are just the tip of the iceberg of what you're supposed to know, and expected to deliver on if and when you get the job.

5. Thanks but nobody really explained to me whats going on. I don't understand the code or what the &0xf and >> are doing. Thanks

6. Is this a job interview, to you?

7. Originally Posted by dnysveen
Thanks but nobody really explained to me whats going on. I don't understand the code or what the &0xf and >> are doing. Thanks
FAQ > Explanations of... > Bit shifting and bitwise operations
FAQ > Prelude's Corner > Bit manipulation

8. The (x)&0xf is to get the lowest 4 bits, and thus a number from 0 to 15 inclusive. That gives the index of the lookup table for the number of bits in that nibble.

The >> is needed to right shift by 4 bits so that each nibble can be checked.

This might be a clearer example:
Code:
```int countBitsInLowestNibble(int nibble)
{
static int table[] = {0,1,1,2,1,2,2,3, 1,2,2,3,2,3,3,4 };
return table[nibble & 0xf]; // lookup number of bits in lowest nibble
}

int countBitsInInt(int x)
{
int count = 0;
int numNibbles = sizeof(int) + sizeof(int);
// cycle through each nibble starting with lowest nibble
for (int i = 0; i < numNibbles; ++i)
{
count += countBitsInLowestNibble(x);
x >>= 4; // place next 4 bits in lowest nibble position
}
return count;
}```

9. Sorry, but if you can't figure out what 0xf is doing, you ain't fit for any C or C++ job.

10. I get the shiffting and nibble part now but I don't understand the table. Why does the table have these values.

Edit
Never mind got it. So when the say count the number of bit it means count the bits that are set to 1?

11. Well, now that you say you've got it all figured out, keep that bit of knowledge safe and if the question ever comes up again in the future you might just consider using something easier:
Code:
```#include <limits>
#include <bitset>
#include <iostream>

std::cout << std::bitset<std::numeric_limits<int>::digits>(your_int_value_here).count() << std::endl;```
Replace your_int_value_here with whatever integer value or variable to get a count of the number of enabled bits for that value/variable.

Originally Posted by dnysveen
So when the say count the number of bit it means count the bits that are set to 1?
Yes, the point seems to be to count the bits in an integer that are set to 1... which is what the above bitset example does for you.

12. What does the limits class do btw, can't find that in the reference (I think you mean to put numeric_limits as well)

also if you want to illustrate it you can do something like
Code:
```int bit_counter(int x)
{

int count = 0;

while(x != 0)
{
count += x & 0x1;
x >>= 1;
}
return count;
}

int main()
{
std::cout << bit_counter(15) << std::endl;

return 0;
}```
der!

Totally missed the count portion of the bitset class, kind of makes this useless.

13. What does the limits class do btw, can't find that in the reference (I think you mean to put numeric_limits as well)
Yes, I've changed the numeric_limits thing, thanks for pointing that out. When you create a bitset, you must specify how many bits you want it to handle. I just put in the numeric_limits part to automatically get that for you so you don't have to guess how many bits are contained in an int.

14. I see, since not all computers have the same size for the types.

15. >> std::numeric_limits<int>::digits
That will return the number of digits that an int can have, not the number of bits. You want:
Code:
`std::cout << std::bitset<sizeof(int)*CHAR_BIT>(your_int_value_here).count() << std::endl;`
I don't remember offhand where CHAR_BIT is defined.