Number of 1 Bits
Last Updated: March 20, 2026
Understanding the Problem
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 classic bit manipulation problem. The straightforward way is to check each bit one by one, but there's a clever trick using n & (n - 1) that lets us skip over the zero bits entirely. And if this function gets called millions of times, we can precompute results in a lookup table for constant-time answers.
Key Constraints:
1 <= n <= 2^31 - 1→ The input is a 32-bit positive integer. This means we have at most 31 bits to inspect, so even a bit-by-bit scan is effectively O(1). The optimization question here isn't about asymptotic complexity, it's about reducing the constant factor.- Since the input is bounded at 31 bits, any approach that loops over the bits runs in O(32) = O(1) time. Brian Kernighan's algorithm improves the loop count from 32 iterations to k iterations (where k is the number of set bits), and a lookup table eliminates the loop entirely.
Approach 1: Check Each Bit
Intuition
The most natural way to count set bits: look at each bit position one at a time. We can check the least significant bit using n & 1 (which is 1 if the bit is set, 0 otherwise), then right-shift n to move the next bit into position. Repeat until all bits are processed.
Since n is at most 31 bits, this loop runs at most 31 times. Simple and effective.
Algorithm
- Initialize a counter
countto 0. - While
nis greater than 0: - If
n & 1equals 1, incrementcount. - Right-shift
nby 1. - Return
count.
Example Walkthrough
Code
- Time Complexity: O(1). We iterate at most 31 times (the number of bits in a 32-bit integer). This is constant regardless of the input value.
- Space Complexity: O(1). We only use a single counter variable.
The loop always runs up to 31 times, even if only 1 bit is set. What if we could skip straight to the set bits and ignore all the zeros in between?
Approach 2: Brian Kernighan's Algorithm
Intuition
Here's the key trick: n & (n - 1) clears the lowest set bit of n. Why? When you subtract 1 from a number, it flips the lowest set bit to 0 and all the bits below it to 1. When you AND the original number with this result, the lowest set bit disappears, and everything below it becomes 0.
So instead of checking every bit position, we just keep clearing the lowest set bit until n becomes 0. The number of times we do this equals the number of set bits. If a number has only 2 set bits out of 31, we loop just twice.
When you subtract 1 from a binary number, the rightmost 1 becomes 0, and all the 0s to its right become 1s. For example, 1010 - 1 = 1001. The AND operation between n and n-1 keeps everything above the rightmost set bit unchanged and zeros out the rightmost set bit along with everything below it. This is why each iteration eliminates exactly one set bit.
Algorithm
- Initialize a counter
countto 0. - While
nis greater than 0: - Clear the lowest set bit:
n = n & (n - 1). - Increment
count. - Return
count.
Example Walkthrough
Code
- Time Complexity: O(k), where k is the number of set bits. The loop runs exactly k times, once per set bit. In the worst case (all bits set), k = 31, so this is still O(1). But in practice, it's faster than Approach 1 for numbers with few set bits.
- Space Complexity: O(1). Only a single counter variable is used.
Brian Kernighan's is great for a single call, but what if hammingWeight is called millions of times in a hot loop? Each call still requires a loop. What if we precomputed the bit count for every possible input chunk and turned the problem into a series of lookups?
Approach 3: Lookup Table
Intuition
This approach directly answers the follow-up question. We precompute the number of set bits for every possible byte value (0 to 255) and store them in a table. Then for any 32-bit integer, we split it into 4 bytes and sum up 4 table lookups. Each lookup is O(1), so the entire operation is O(1) with no loops at all.
The trade-off is 256 entries of precomputed data, which is trivial in terms of memory but makes each call blazing fast.
Algorithm
- Build a table of size 256 where
table[i]stores the number of set bits ini. - For the input
n, extract each of its 4 bytes using bit masking and shifting. - Look up each byte in the table and sum the results.
- Return the sum.
Example Walkthrough
Code
- Time Complexity: O(1). Building the table is O(256) = O(1), and each query is 4 lookups = O(1). If the table is prebuilt and shared across calls, each query is purely O(1).
- Space Complexity: O(1). The lookup table uses 256 entries, which is a fixed constant independent of the input.