</>EmbeddedInterview
← All problems · Bit Manipulation

Count the Set Bits

Easy

Implement popcount(uint32_t x) that returns the number of 1 bits in x. Your loop should run once per set bit, not once per bit.

Write your code on the right and press Run (or Ctrl + Enter). Hidden tests check your functions and print the result below the editor.

What does x & (x - 1) do to the lowest set bit?

#include <stdio.h>
#include <stdint.h>

unsigned popcount(uint32_t x)
{
    unsigned n = 0;
    while (x) {
        x &= x - 1;   /* clear lowest set bit */
        n++;
    }
    return n;
}

Subtracting 1 flips the lowest set bit to 0 and all bits below it to 1; ANDing with the original clears exactly that bit. The loop runs once per set bit (Brian Kernighan's algorithm), so it is fast for sparse values.

For constant time, use the SWAR (parallel bit count) method, or a 16-entry nibble lookup table. In real code, __builtin_popcount lets the compiler pick the best instruction sequence for the target.

solution.c
OutputPress Run to compile and test your code.
Show the hidden tests
/* ---- tests ---- */
static int fails;
#define CHECK(c) do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); fails++; } } while (0)
int main(void)
{
    CHECK(popcount(0) == 0);
    CHECK(popcount(1) == 1);
    CHECK(popcount(0xFFu) == 8);
    CHECK(popcount(0x80000001u) == 2);
    CHECK(popcount(0xFFFFFFFFu) == 32);
    CHECK(popcount(0xA5A5A5A5u) == 16);
    puts(fails ? "Some tests failed" : "All tests passed");
    return fails != 0;
}