We're given a positive integer and need to count how many bits in its binary form are 1. For instance, the number 11 in binary is 1011, so the answer is 3.

This is a bit manipulation problem. The direct approach checks each bit one by one. A faster variant uses n & (n - 1) to skip over the zero bits and touch only the set bits. And if the function gets called millions of times, a precomputed lookup table answers each query with a handful of array accesses.

Key Constraints:

Intuition

Count set bits by looking at each bit position one at a time. The expression n & 1 is 1 if the least significant bit is set and 0 otherwise. After inspecting that bit, right-shift n to move the next bit into the least significant position, and repeat until n reaches 0.

Since n has at most 31 bits, this loop runs at most 31 times.

Algorithm

Example Walkthrough

Code

This loop runs once per bit position, so it touches every zero bit even when only one bit is set. The next approach iterates once per set bit instead, skipping the zeros entirely.

Intuition

The expression n & (n - 1) clears the lowest set bit of n. Subtracting 1 flips that lowest set bit to 0 and turns every bit below it into a 1, while leaving every bit above it unchanged. ANDing n with that result keeps the high bits as they were, zeros out the lowest set bit, and zeros out everything below it (those positions are 0 in n). The net effect is that exactly one set bit, the lowest, is removed.

So instead of checking every bit position, keep clearing the lowest set bit until n becomes 0. The number of iterations equals the number of set bits. A number with 2 set bits out of 31 loops twice, not 31 times.

Algorithm

Example Walkthrough

Code

Brian Kernighan's algorithm still runs a loop on every call. When hammingWeight is invoked many times, the follow-up asks how to do better. The next approach precomputes the bit count for every possible byte and replaces the loop with a fixed number of table lookups.

Intuition

This approach answers the follow-up. Precompute the number of set bits for every byte value (0 to 255) and store them in a 256-entry table. A 32-bit integer is four bytes, so counting its set bits becomes four table lookups added together, with no per-bit loop.

The cost is 256 entries of precomputed data, a fixed amount of memory that is reused across every call. In exchange, each query after the table is built costs four array accesses and three additions.

Algorithm

Example Walkthrough

Code