Master of Lowbit

题号：NC237178
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Lowbit is a well-known operation which is widely used in Fenwick tree. The $\texttt{lowbit}$ of an integer $x$ is the value of the lowest $1$ in the binary representation of $x$ .

For example, $\texttt{lowbit}$ $6$ equals to $2$ , since the binary representation of $6$ is $(110)_2$ , and $(10)_2$ is the value of the lowest $1$ . $\texttt{lowbit}$ $20$ equals to $4$ , since the binary representation of $20$ is $(10100)_2$ , and $(100)_2$ is the value of the lowest $1$ .

One day, Little Y wants to test your knowledge of $\texttt{lowbit}$ and gives you one integer $x$ . In each step, you can do one of the following operations to $x$ :

$x := x + lowbit(x)$
$x := x - lowbit(x)$

You need find out the minimum number of steps to let $x$ become $0$ .

输入描述:

One integer  -- the number Little Y gives you.

输出描述:

One integer indicating the minimum number of steps.

示例1

输入

复制

输出

复制

示例2

输入

复制

输出

复制

说明

For the second example, the 3 steps are: