#P1074. 加一乘二

加一乘二

题目描述

你有一个数字 1,你可以对它进行若干次操作。每次操作要么把它乘以 2,要么把它加上 1,请问至少几次操作可以让它恰好等于 nn

输入格式

输入一行一个正整数。

输出格式

输出一行一个正整数表示答案。

3
2
15
6

样例解释2

样例 2 说明:先做两次加一运算得到 3,然后做一次乘二运算得到 6,然后做一次加一运算得到 7,做一次乘二运算得到 14,再加一得到 15,共 6 次运算

数据规模与约定

测试点编号 nn\leq
1-2 10
3-4 20
5-6 10510^5
7-8 10910^9
9-10 101810^{18}