31373번 - Add and Reverse 다국어

문제

Consider a non-negative integer $x$ stored in 32ドル$ bits of memory: $$x = b_{31} \cdot 2^{31} + b_{30} \cdot 2^{30} + \ldots + b_{2} \cdot 2^{2} + b_{1} \cdot 2^{1} + b_{0} \cdot 2^{0}$$ where each bit $b_{i}$ can take two values 0ドル$ and 1ドル$ independently of other bits.

We perform a sequence of operations with this integer, possibly an empty one. In one operation, we can either increase the number by one or reverse the bits constituting it: swap 31ドル$-st bit and 0ドル$-th bit, swap 30ドル$-th bit and first bit, $\ldots,ドル swap 16ドル$-th bit and 15ドル$-th bit. We can perform any number of any of these two operations in any order.

What is the minimum possible number of operations required to transform a zero to the given integer $n$?

The increasing by one is carried out modulo 2ドル^{32},ドル which means that, if the current number is equal to 2ドル^{32} - 1,ドル increasing it by one produces a zero.

입력

The only line contains an integer $n$ (0ドル \le n < 2^{32}$).

출력

Print one integer: the minimum possible number of operations required to transform a zero to the given integer $n$.

제한

힌트

In the first example, the fastest way to get a 5ドル$ is to increase the number by one five times.

In the second example, we start by producing a one, and then reverse the bits, turning 1ドル = 2^{0}$ into 2ドル,147円,483円,648円 = 2^{31}$.