Program to count the number of bits set in c

Question

I have tried to count the number of bits set in an integer value in C. But for some values it is showing the correct bit set count and for some values it is not.

PFB program code

int main()
{
    int a = 512, i = 0, j = 1, count = 0, k = 0;

    for (i = 0; i < 31; i++)
    {
        if (k = a & j)
        {
            count++;
            j = j << 1;
        }
    }
    printf("the total bit set count is %d", count);
}

The output of set bit value count of 512 is showing as zero and if the value used is 511 count is showing as 9.

Please help me to correct the program.

Answer 1

Stanford University has a page of different ways to implement common bit-twiddling operations. They list 5 different algorithms to count the bits set, all with C examples.

https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

Their simplest implementation:

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; v >>= 1)
{
  c += v & 1;
}

Answer 2

If you're using gcc/clang compiler, you can use the builtin function __builtin_popcount

unsigned int user_input = 100
int count = __builtin_popcount(n); // count == 3

When I'm not looking for cross-platform I'll use this function since its highly optimised.