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

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...

> 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.

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

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

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

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?

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.

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.

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.