整数替换如何用位运算贪心？奇数时为什么看末两位？

简化版

整数替换中，偶数直接除以 2；奇数要在 n+1 和 n-1 中选择。贪心思路是让下一步得到的偶数含有更多尾随 0，这样能连续除以 2。通常若 n == 3 或末两位是 01，选 n-1；若末两位是 11，选 n+1。

详细版

偶数没有选择，n/2 最优。奇数加一或减一都会变偶数，区别在于变成的偶数能除以 2 多少次。观察二进制末尾：...01 减一会得到更多尾随 0，...11 加一通常会产生进位并得到更多尾随 0。但 3 是特例，3 -> 2 -> 1 比 3 -> 4 -> 2 -> 1 更短。

实现时要用 long 保存 n，因为 Integer.MAX_VALUE + 1 会溢出。时间复杂度 O(log n)。

完整版教学

一、为什么偶数没有选择

规则是：

偶数：n -> n / 2
奇数：n -> n + 1 或 n - 1

偶数只能除以 2，这一步既合法又会最快缩小数字规模。比如 16 -> 8 -> 4 -> 2 -> 1，每步都直接砍半。

奇数才是这题的决策点。

二、奇数为什么要看下一步能除几次 2

奇数加一或减一都会变偶数。变成偶数后，如果末尾有多个 0，就可以连续除以 2。

7 = 111
7 + 1 = 1000，可以连续除 3 次
7 - 1 = 110，只能先除 1 次

所以局部目标是让奇数调整后产生更多尾随 0。

三、末两位规则怎么来

奇数二进制末位一定是 1，只需看倒数第二位：

末两位	倾向操作	原因
`01`	`n-1`	变成 `00`，产生尾随 0
`11`	`n+1`	进位后通常产生更多尾随 0

记忆钩子：奇数看末两位，01 往下，11 往上，唯独 3 往下。

用代码判断就是 (n & 3)。

四、为什么 3 是特例

3 的二进制是 11，按普通规则似乎应该 +1：

3 -> 4 -> 2 -> 1，共 3 步

但选择 -1 更短：

3 -> 2 -> 1，共 2 步

所以要单独判断 n == 3 时减一。

五、代码模板

int integerReplacement(int n) {
    long x = n;
    int steps = 0;
    while (x != 1) {
        if ((x & 1) == 0) {
            x >>= 1;
        } else if (x == 3 || (x & 3) == 1) {
            x--;
        } else {
            x++;
        }
        steps++;
    }
    return steps;
}

x & 1 判断奇偶，x & 3 取末两位。使用 long 是为了避免 2147483647 + 1 溢出。

六、用例子推演

n=7：

7(111) 末两位 11，且不是 3，选 +1
8(1000) -> 4 -> 2 -> 1
总 4 步

n=15：

15(1111) +1 => 16
16 -> 8 -> 4 -> 2 -> 1

如果选 15-1=14，还要 14->7，又回到奇数决策，通常更慢。

七、常见误区与追问

误区：所有奇数都减一。 7、15 这类末两位为 11 的数，加一通常更快。
误区：所有末两位 11 都加一。 3 是特例，减一更短。
误区：用 int 处理最大值。 Integer.MAX_VALUE + 1 会溢出，应用 long。
追问：为什么看末两位就够？ 奇数加减一后的尾随 0 数量主要由低位进位/借位决定。
追问：复杂度为什么是对数？ 大多数步骤会右移除以 2，数字规模快速缩小。
追问：这算严格证明吗？ 面试中可用尾随 0 贪心解释，严谨证明可结合低位分类和特例分析。

八、加强记忆

整数替换的口诀是“偶数右移，奇数看末两位”。01 减一，11 加一，因为目标是制造更多尾随 0，方便连续除以 2；但 3 必须减一。最后用 long 扛住最大 int，这是实现红线。

简化版

详细版