Why it works
- Subtracting 1 borrows from the lowest 1: that 1 becomes 0, the zeros under it become 1s, and every bit above it stays the same. So n & (n - 1) is n with exactly its lowest 1 cleared.
- Each round clears one 1 and counts it, and the loop stops at 0, when no ones are left. So count ends equal to the number of ones.
- The loop runs once per 1, not once per bit: 90 has 7 bits, but the run takes 4 rounds. Reading the bits one by one would take 7, and 32 on LeetCode.
Complexity
Time O(k), where k is the number of ones: one round per 1, at most 32 on LeetCode. Memory O(1): two numbers and the count.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗