Count and isolate set bits
Derive low-bit operations and use C++ bit utilities with valid unsigned inputs.
Understand the idea
For nonzero unsigned x, x & (x − 1) clears the lowest set bit: subtracting one flips that bit to zero and all trailing zeros to ones. Repeating the operation counts set bits. A power of two has exactly one set bit, so test x != 0 and (x & (x − 1)) == 0.
Trace a small example
For 12 (1100), one clearing step produces 8 (1000), and the next produces 0. Thus its population count is 2. C++20 and later provide std::popcount and std::has_single_bit in <bit>; std::countr_zero also has a defined result for zero, unlike some older compiler builtins.
#include <bit>
#include <iostream>
int main() {
unsigned long long x = 22;
std::cout << std::popcount(x) << '\n';
while (x != 0) {
x &= x - 1;
std::cout << x << '\n';
}
}Conditions and cost
A clearing loop performs O(number of set bits) iterations. Unsigned arithmetic provides the modular wraparound used by low-bit identities. Do not transfer assumptions about standard utilities to compiler-specific builtins without reading their contracts.
Why must the power-of-two test reject zero explicitly?
Turn the idea into code
Trace clearing the lowest set bit from 22 until zero.
Give me a hint
Write 22 as 10110.
Show the explained solution
22 → 20 → 16 → 0. Three clearing steps mean three set bits.
Your notes
Mark complete when you can explain it yourself.