题目描述

给定一个正整数 $n$，计算 $n$ 在二进制表示下有多少个 $1$。

例如：

• $n = 3$ 时，二进制为 $(11)_2$，有 $2$ 个 $1$；
• $n = 4$ 时，二进制为 $(100)_2$，有 $1$ 个 $1$；
• $n = 7$ 时，二进制为 $(111)_2$，有 $3$ 个 $1$。

输入格式

一行，一个正整数 $n$。

输出格式

一行，一个整数，表示 $n$ 的二进制表示中 $1$ 的个数。

样例

3

2

4

1

数据范围

• $1 \le n \le 10^{15}$