整数替换

偶数最省 · n = 8：先看最简单的纯偶数 8。下面 5 个格子是它的二进制。偶数 = 末位是 0,/2 就是整体右移一位,不丢信息、最省。

8 是偶数 · /2：末位的 0 被丢掉,1 整体右移。8 变 4,走了 1 步。

4 是偶数 · /2：还是偶数,再右移一位。4 变 2,第 2 步。

2 是偶数 · /2：再右移到只剩末位的 1,到达 1!8 共走 3 步。偶数全程一路 /2,毫无悬念。

二进制里末位连续的 0 越多,接下来能连着 /2 的次数就越多。所以奇数时要选「让低位多出 0」的那一边——这就是全题的贪心核心。

把奇数末两位 11 加 1,会像多米诺一样进位,低位连出好几个 0;末两位 01 减 1 直接得 0。盯住下面要演的末两位。

主线演示 · n = 7：换个奇数 7 走全程。7 的二进制是 00111,是奇数(末位 1),要决定 +1 还是 −1。

看 7 的末两位 = 11：把最右边两个格子圈出来:11。按口诀,末两位是 11 就 +1——加 1 会触发连续进位,低位一下清出两个 0。

7 + 1 = 8：7 + 1 = 8。看二进制:末尾 111 全进位翻成 000,只在高位冒出一个 1。低位三个 0意味着接下来能连 /2 三次!第 1 步。

8 是偶数 · /2：现在是偶数,右移一位。8 变 4,第 2 步。

4 是偶数 · /2：还是偶数,继续右移。4 变 2,第 3 步。

2 是偶数 · /2：最后一步右移到 1!7 全程 7→8→4→2→1,共 4 步。当初选 +1 制造的三个 0,直接换来三次连除。

反例:7 若选 −1 会怎样?：假如 7 偷懒选 −1 得 6(00110),只清出一个末位 0;接着 6→3 又是奇数还得抉择。绕一圈才到 1,印证了「末两位 11 该 +1」。

再演一例 · n = 15：再看 15(01111)。奇数,末两位是 11——又该 +1,而且这次进位能清出一长串 0。

看 15 末两位 = 11 · +1：圈出末两位 11,按规则 +1。15 + 1 = 16,马上看二进制会变成什么样。

15 + 1 = 16：16 = 10000:低位四个 0排成一排!接下来能一口气连除 4 次 /2。第 1 步。

16 → 8 · /2：偶数右移。16 变 8,第 2 步。

8 → 4 · /2：继续右移。8 变 4,第 3 步。

4 → 2 · /2：再右移。4 变 2,第 4 步。

2 → 1 · 完成：最后右移到 1!15 全程 5 步。一次聪明的 +1 把后面铺成了 4 次连除——这就是末两位 11 选 +1 的威力。

对照:末两位 01 该 −1：反过来,若奇数末两位是 01(如 5),−1 直接把末位的 1 抹成 0;若硬要 +1 反而得 6,低位只多一个 0、还更大。所以 01 选 −1。

特例:n = 3 必须 −1：唯一的例外:3 末两位也是 11,但它太小——−1 走 3→2→1 只要 2 步,+1 走 3→4→2→1 反而 3 步。所以规则要单独把 n==3 拦下来选 −1。

边界三连：先想 n=1(零步)、n=3(特例 −1)、n=INT_MAX(溢出陷阱)三种,代码就稳了。

面试追问：把「贪心为何看末两位」「O(log n)」「long 防溢出」讲清楚,是这题面试的得分点。