题目描述

给定一个整数 $n$，你可以进行若干次操作。

每次操作可以翻转 $n$ 的二进制表示中的某一位，即：

• 将 $0$ 变成 $1$；
• 将 $1$ 变成 $0$。

请问：至少需要多少次操作，才能将 $n$ 变成 $n-1$。

输入格式

输入一个正整数 $n$。

$1 < n \le 10^9$。

输出格式

输出最少需要的操作次数。

样例

10

2

样例解释

$10$ 的二进制表示为：$1010$

$9$ 的二进制表示为：$1001$

因此最少需要两步：

$1010 \rightarrow 1000 \rightarrow 1001$

数据范围

$1 < n \le 10^9$。