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}$.