题目描述

你有一个初始值为 $1$ 的数字。每次操作，你可以执行以下两种操作之一：

1. 将当前数字乘以 $2$
2. 将当前数字加上 $1$

求最少需要多少次操作，才能使数字恰好变为 $n$。

输入格式

一行一个正整数 $n$。

输出格式

一行一个正整数，表示最少操作次数。

样例

3

2

15

6

8

3

样例解释

对于样例 1：$1 \xrightarrow{+1} 2 \xrightarrow{+1} 3$，共 2 次操作。

对于样例 2：$1 \to 2 \to 3 \to 6 \to 7 \to 14 \to 15$（两次 $+1$，一次 $\times 2$，一次 $+1$，一次 $\times 2$，一次 $+1$），共 6 次。

对于样例 3：$1 \xrightarrow{\times 2} 2 \xrightarrow{\times 2} 4 \xrightarrow{\times 2} 8$，共 3 次操作。

数据范围与约定

下发样例

下发样例下载