描述

小招喵喜欢在数轴上跑来跑去，假设它现在站在点n处，它只会3种走法，分别是：

1.数轴上向前走一步，即n=n+1 

2.数轴上向后走一步,即n=n-1 

3.数轴上使劲跳跃到当前点的两倍，即n=2*n

现在小招喵在原点，即n=0，它想去点x处，快帮小招喵算算最快的走法需要多少步？

输入描述：

小招喵想去的位置x

输出描述：

小招喵最少需要的步数

解题思路

首先给出几个显而易见的推论：

1、从0走到x，和从0走到-x，用的步数是相同的，因此只要考虑正数。

2、从0走到x的步数，和从x走到0是一样的，因此可以反向计算。

3、反向计算的情况下，按照贪心的思想，若x为偶数，那么直接除以2就是最优解，若x为奇数，则要考虑+1或者-1哪个更优秀，这也是本题的关键。

我的想法是，将x-1和x+1这两个数分别表示成二进制数，比较其中1的个数，个数越少的越优秀；若1的个数相同，那么取数字更小的x-1。

原因很简单，除以2的效率比±1的效率要高多了，所以应该让-1或+1后的数字末尾的0尽可能多，相应的，就是让1尽可能少。

举一个例子，若x = 23，那么将其变成22或者24，哪个才是最优解？分别列出来

22，11，10，5，4，2，1，0。 一共是8步。

24，12，6，3，2，1，0。 一共是7步。

而22的二进制数为10110，一共3个1；24的二进制数为11000，只有2个1，确实符合结论。

下面贴出c++代码。

#include <iostream>
using namespace std;

//计算x的二进制表示中包含1的个数
int count1(int x) {
    int res = 0;
    while (x) {
        if (x & 1) ++res;
        x >>= 1;
    }
    return res;
}

int main() {
    int x;
    cin >> x;
    if (x < 0) x = -x;
    int ans = 0;
    while (x) {
        if (x & 1) { //奇数的情况下比较-1和+1哪个更优秀
            if (count1(x - 1) <= count1(x + 1)) {
                --x;
            } else {
                ++x;
            }
        } else { //偶数的情况下直接除以2
            x >>= 1;
        }
        ++ans;
    }
    cout << ans;
}