Bit Counting (Popcount & Brian Kernighan's Algorithm)
Bit Counting computes the Hamming weight (number of 1-bits) of an integer using Brian Kernighan's n & (n - 1) loop, DP over 0..n, or O(1) hardware __builtin_popcount.
Difficulty: Easy · Interactive Visualizer · C++ / Python / Java / JS Code
Bit Counting (Popcount & Brian Kernighan's Algorithm)
Counting the number of set (1) bits in an integer—its Hamming weight or popcount—appears everywhere from Bitmask DP to Bloom Filters and error-correcting codes. Brian Kernighan's Algorithm clears the lowest set bit with n &= (n - 1) on each iteration, looping only as many times as there are 1-bits!
At a Glance
| Method | Time Complexity |
| :--- | :---: |
| Brian Kernighan (n &= n - 1) | $O(\text{set bits})$ |
| DP for All 0..n (dp[i] = dp[i >> 1] + (i & 1)) | $O(n)$ total ($O(1)$ per number) |
| Hardware Instruction (__builtin_popcount / std::popcount) | $O(1)$ (single CPU POPCNT instruction) |
---
Practice Problems
Easy
1. Brian Kernighan's Popcount & Counting Bits for 0..n (LeetCode 191 & 338)
Compute the Hamming weight of a single integer with Kernighan's trick, and compute popcount for all integers 0..n in $O(n)$ DP.
Approach: dp[i] = dp[i >> 1] + (i & 1) (or dp[i] = dp[i & (i - 1)] + 1). Time: $O(n)$.
<details>
<summary>Show C++ Solution</summary>
#include <cstdint>
#include <iostream>
#include <vector>
int kernighanPopcount(uint32_t n) {
int cnt = 0;
while (n) { n &= (n - 1); ++cnt; }
return cnt;
}
std::vector<int> countBitsUpTo(int n) {
std::vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; ++i) dp[i] = dp[i >> 1] + (i & 1);
return dp;
}
int main() {
std::cout << kernighanPopcount(29) << " | "; // 0b11101 -> 4
for (int x : countBitsUpTo(5)) std::cout << x << " ";
std::cout << "\n"; // 4 | 0 1 1 2 1 2
return 0;
}
</details>
---