Number of Bits

Given an integer n, return the number of 1 bits in n.

Constraints

• 0 ≤ n < 2 ** 31

https://binarysearch.com/problems/Number-of-Bits

Examples

Example 1

Input

• n = 0

Output

• answer = 0

Example 2

Input

• n = 3

Output

• answer = 2

Explanation

3 is 11 in binary.

Example 3

Input

• n = 1

Output

• answer = 1

Example 4

Input

• n = 4

Output

• answer = 1

Explanation

4 is 100 in binary.

Example 5

Input

• n = 2

Output

• answer = 1

Explanation

2 is 10 in binary.

Solution