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

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

示例 1：

  1. 输入：n = 8
  2. 输出：3
  3. 解释：8 -> 4 -> 2 -> 1

示例 2：

  1. 输入：n = 7
  2. 输出：4
  3. 解释：7 -> 8 -> 4 -> 2 -> 1
  4. 或 7 -> 6 -> 3 -> 2 -> 1

示例 3：

  1. 输入：n = 4
  2. 输出：2

提示：

  • 1 <= n <= 2^31 - 1

解法一：递归

这里解释下几个位运算点：

  • n&1 就相当于是 n % 2
  • n>>1 如果是 偶数 那就是 n/2 ，如果是基数那就是 n/2向下取整也即是 n-1/2，所以如果我们想要得到 n+1/2，那么就可以使用 n>>1+1 ```go func integerReplacement(n int) int { if n == 1 {
    1.   return 0
    } if n&1 == 0 {
      return integerReplacement(n>>1) + 1
    } return min(integerReplacement(n>>1), integerReplacement(n>>1+1)) + 2 }

func min(params …int) int { res := params[0] for _, val := range params { if val < res { res = val } } return res }

<a name="E8DH4"></a>
## 解法二： 位运算
这里大致其实都能想到只是有一个点 
```go
7 -> 6 -> 3 -> 2 -> 1
7 -> 8 -> 4 -> 2 -> 1

这俩流程看起来一样，但实际上区别是前者是两次减法两次除法，后者是一次加法三次除法。所以实际上还是后者更优一些。
那么这也就是对应到了当前 n 与4 的关系。
这里用到 n&2，这里就相当于是 (n+1)/2%2 从 1 到 7分别是：0,0,2,0,0,2,2
其中特例是 3， 3 -> 4 -> 2 -> 1 比 3 -> 2 -> 1多一个流程

func integerReplacement(n int) int {
    res := 0
    for n > 1 {
        res++
        if n&1 == 0 {
            n >>= 1
        } else if n == 3 {
            n--
        } else if n&2 == 2 {
            n++
        } else {
            n--
        }
    }
    return res
}