Number of 1 Bits

Number of 1 Bits

Given a positive integer n, return the number of set bits (1s) in its binary representation. This is also known as the Hamming weight.

Examples

Example 1:

Input: n = 11
Output: 3
Explanation: 11 in binary is 1011, which has three set bits.

Example 2:

Input: n = 128
Output: 1
Explanation: 128 in binary is 10000000, which has one set bit.

Example 3:

Input: n = 2147483645
Output: 30
Explanation: 2147483645 in binary is 1111111111111111111111111111101, which has 30 set bits.

Constraints

• 1 <= n <= 2^31 - 1

Expected Complexity

• Time: O(log n) or O(k) where k is the number of set bits
• Space: O(1)