JuniorCodeVery commonNot answered yet
Count the number of set bits in an integer
Return the number of set bits (1s in the binary representation) of a 32-bit unsigned integer.
Requirements:
O(32) bit-by-bit scan on sparse inputs.
- Aim for O(k), where k is the number of set bits — better than a fixed
- Use an unsigned type to avoid UB from shifting negative values.
- Do not call
std::popcount; implement the counting yourself.
int countBits(uint32_t n) {
// your code here
}Write the implementation.
Use Kernighan's trick: n &= n - 1 clears the lowest set bit, repeat until n is 0 — runs in O(k) where k is the number of set bits. In C++20 prefer std::popcount, which compiles to a single instruction.
- ✗Using a naive bit-by-bit loop (O(32)) instead of Kernighan's trick (O(set bits))
- ✗Not handling negative numbers correctly when the argument is a signed int — use unsigned
- ✗Forgetting about
std::popcountin C++20 which makes this a one-liner
- →How would you check if a number is a power of two using bit manipulation?
- →What does
n & (n-1)do in general?
Contents
Task
Write a function that takes an integer and returns the number of set bits (1s in binary representation).
Solution
#include <bit> // std::popcount (C++20)
#include <cstdint>
#include <cassert>
// --- Modern (C++20) ---
int countBitsModern(uint32_t n) {
return std::popcount(n);
}
// --- Kernighan's trick (pre-C++20) ---
int countBitsKernighan(uint32_t n) {
int count = 0;
while (n) {
n &= n - 1; // clears the lowest set bit
++count;
}
return count;
}
int main() {
assert(countBitsKernighan(0) == 0);
assert(countBitsKernighan(1) == 1);
assert(countBitsKernighan(0xFF) == 8);
assert(countBitsKernighan(0b1011) == 3);
assert(countBitsKernighan(UINT32_MAX)== 32);
}Key points
n &= n - 1clears exactly one (lowest) set bit per iteration.- Runs in O(k) iterations where k is the number of set bits, not O(32).
- In practice prefer
std::popcount<uint32_t>(C++20) — compiles to a singlePOPCNTinstruction on x86. - Use unsigned types to avoid UB on right-shifting negative values.
Contents
