Write a positive integer n in base 2 and count how many of its digits are 1. Return that count. (This count is often called the number's population count or Hamming weight.)
Example 1
Input: n = 22
Output: 3
22 = 16 + 4 + 2, which is 10110 in binary.
Example 2
Input: n = 1024
Output: 1
1024 is a power of two, 10000000000 in binary, so it has a single 1.
Example 3
Input: n = 2147418367
Output: 23
In binary this is fifteen 1s, then eight 0s, then eight 1s.
Constraints
1 <= n <= 2³¹ - 1, so n always fits in a signed 32-bit integer and is never negative.Read the lowest binary digit with n & 1, then drop it with a right shift. Repeat until n is 0, counting the 1s you see.
The computer already stores n in binary, so there's nothing to convert. The question is only how to read the digits one at a time. Two operations do it:
Time O(number of 1 bits)Space O(1)
The full walkthrough and code are part of Premium
22
3