177. Number of 1 Bits
You receive a single non-negative integer n. Write out n in base 2 and count how many of its digits are 1 — this count is often called the population count or Hamming weight of n. Return that count as an integer.
For instance, n = 11 is 1011 in binary, which contains three 1s, so the answer is 3.
A straightforward loop over the bits works — but can you make the number of loop iterations depend only on how many 1 bits there actually are?
Example 1:
Input: n = 11
Output: 3
Explanation: 11 in binary is 1011. Three of the four digits are 1.
Example 2:
Input: n = 128
Output: 1
Explanation: 128 is a power of two, so its binary form 10000000 has exactly one set bit.
Example 3:
Input: n = 2147483645
Output: 30
Explanation: 2147483645 is 1111111111111111111111111111101 in binary — 31 digits, all 1 except the second-lowest.
Constraints:
- 0 ≤ n ≤ 2³² - 1
Hints:
n & 1 tells you whether the lowest bit is set, and n >> 1 discards it. Repeat until n becomes 0.
The expression n & (n - 1) erases exactly the lowest set bit of n. Counting how many times you can do that before hitting 0 counts the 1 bits directly — one iteration per set bit.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 11
Expected output: 3