Bit-counting tricks in C

Classic bit hacks with & and subtraction.

int popcount(unsigned n) {
    int count = 0;
    while (n) {
        n &= n - 1;  /* clears the lowest set bit */
        count++;
    }
    return count;
}

int is_power_of_two(unsigned n) {
    return n != 0 && (n & (n - 1)) == 0;
}

How it works

1. n &= n - 1 clears the lowest set bit each pass.
2. Counting the passes gives the population count.
3. The same identity detects powers of two.

Keywords and builtins used here

• int
• is_power_of_two
• popcount
• return
• unsigned
• while

The run, in numbers

Lines

12

Characters to type

199

Tokens

62

Three-star pace

100 tpm

At the three-star pace of 100 tokens a minute, this run takes about 37 seconds.

Type this snippet

Step 2 of 2 in Bit manipulation, step 18 of 20 in Data structures & algorithms.

← Previous Next →