191. Number of 1 Bits

1. Description

Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

2. Example

Example 1

Input: n = 11
Output: 3
Explanation:
The input binary string 1011 has a total of three set bits.

Example 2

Input: n = 128
Output: 1
Explanation:
The input binary string 10000000 has a total of one set bit.

Example 3

Input: n = 2147483645
Output: 30
Explanation:
The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

3. Constraints

• 1 <= n <= $2^{31}$ - 1

4. Solutions

Bit Manipulation

Time complexity: O(logn)
Space complexity: O(1)

class Solution {
public:
    int hammingWeight(int n) {
        int bitone_count = 0;
        while (n > 0) {
            n = n & (n - 1);
            ++bitone_count;
        }

        return bitone_count;
    }
};