# 397.整数替换

## 问题描述
[397. 整数替换 (Medium)](https://leetcode.cn/problems/integer-replacement/)

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

1. 如果 `n` 是偶数，则用 `n / 2` 替换 `n`。
2. 如果 `n` 是奇数，则可以用 `n + 1` 或 `n - 1` 替换 `n` 。

返回 `n` 变为 `1` 所需的 最小替换次数 。

**示例 1：**

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

```

**示例 2：**

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

```

**示例 3：**

```
输入：n = 4
输出：2

```

**提示：**

- `1 <= n <= 2³¹ - 1`

## 解题思路
贪心的思想。这里只需要讨论`n`为奇数的情况，如果`n`为奇数，那么`n + 1`和`n - 1`必然有一个能被4整除，如果`(n + 1) % 4 == 0`，那么`n = n + 1`，否则`n = n - 1`，注意`3`是例外。

## 代码
```cpp
class Solution {
  public:
    int integerReplacement(int n) {
        int cnt = 0;
        while (n != 1) {
            while ((n & 1) == 0) { // n为偶数
                n >>= 1;         // 相当于除以2
                cnt++;
            }
            if (n == 1) {
                return cnt;
            }
            if (n == 3)
                return cnt + 2;
            if ((n + 1) & 3 == 0) { // n能被4整除
                n += 1;
                cnt++;
            } else {
                n -= 1;
                cnt++;
            }
        }
        return cnt;
    }
};
```