整数替换

给定一个正整数 n，你可以做如下操作：

1. 如果 n 是偶数，则用 n / 2替换 n。
2. 如果 n 是奇数，则可以用 n + 1或n - 1替换 n。
   n 变为 1 所需的最小替换次数是多少？

示例 1:

输入:
8

输出:
3

解释:
8 -> 4 -> 2 -> 1
示例 2:

输入:
7

输出:
4

解释:
7 -> 8 -> 4 -> 2 -> 1
或
7 -> 6 -> 3 -> 2 -> 1

递归的代码：

class Solution {
public:
    int integerReplacement(int n) {
        if(n == INT_MAX) return 32;
        if(n == 1) return 0;
        if(n % 2 == 0)
            return integerReplacement(n/2) + 1;
        int left = integerReplacement(n + 1) + 1;
        int right = integerReplacement(n - 1) + 1;
        return left < right ? left : right;
    }
};

使用位操作运算代码:

class Solution {
public:
    // 用位运算，最后一位是0直接右移，最后两位都是1，且该数不是3是，就选择+1，
    // 否则就选择－1，直到该数变成1，为防止越界，把n变成长整型
    int integerReplacement(int n) {
        long temp = n;
        int count = 0;
        while(temp != 1) {
            if((temp & 3 )== 3 && temp != 3) {    // 使用&的时候一定要加上()   eg : (temp & 3) 避免优先级问题
                ++temp;
            } else if((temp & 1) == 1) {
                --temp;
            } else {
                temp = temp >> 1;
            }
            ++count;
        }
        return count;
    }
};