题目

给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：

翻转 n 的二进制表示中最右侧位（第 0 位）。
如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。

返回将 n 转换为 0 的最小操作次数。

示例 1：

输入：n = 3 输出：2 解释：3 的二进制表示为 "11" "11" -> "01" ，执行的是第 2 种操作，因为第 0 位为 1 。 "01" -> "00" ，执行的是第 1 种操作。

示例 2：

输入：n = 6 输出：4 解释：6 的二进制表示为 "110". "110" -> "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。 "010" -> "011" ，执行的是第 1 种操作。 "011" -> "001" ，执行的是第 2 种操作，因为第 0 位为 1 。 "001" -> "000" ，执行的是第 1 种操作。

提示：

0 <= n <= 10^9

解题思路

核心规则：

规则 1：可以直接翻转最右边一位（第 0 位）。
规则 2：如果第 $i-1$ 位是 1，且它右边所有位都是 0，才能翻转第 $i$ 位。

我们来看几个简单的例子（$2^k$ 变为 0 的步数）：

$1$ 变为 $0$ (二进制 1 -> 0)：
- 直接用规则 1，翻转第 0 位。
- 共 1 步。
$2$ 变为 $0$ (二进制 10 -> 00)：
- 想把最左边的 1（第 1 位）变成 0，根据规则 2，必须先把它的右边变成 1（即达到 11 的状态）。
- 10 -> 11 (规则 1)
- 11 -> 01 (规则 2，现在第 1 位变 0 了！)
- 01 -> 00 (规则 1)
- 共 3 步。
$4$ 变为 $0$ (二进制 100 -> 000)：
- 想翻转第 2 位，必须先让它右边变成 10（即达到 110）。
- 100 -> 101 -> 111 -> 110 (花了 3 步凑出翻转条件)
- 110 -> 010 (规则 2，终于把最左边的 1 翻掉了！)
- 010 -> 011 -> 001 -> 000 (剩下的 2 变为 0，还需要 3 步)
- 共 7 步。

发现规律 1：

想要单独消除第 $k$ 位的 1（即把 $2^k$ 变为 0），固定需要 $2^{k+1} - 1$ 步。

第 0 位 (1): $2^1 - 1 = 1$ 步
第 1 位 (10): $2^2 - 1 = 3$ 步
第 2 位 (100): $2^3 - 1 = 7$ 步
第 3 位 (1000): $2^4 - 1 = 15$ 步

如果一个数字有多个 1，比如 $6$（二进制 110），该怎么办？

我们想把 110 变为 000。

最大的 1 在第 2 位（价值 4）。按上面的规律，单纯把第 2 位的 1 消除掉原本需要 7 步（从 100 开始算）。

但是，要消除第 2 位，前提条件是“第 1 位是 1，且右边全为 0”（即 110 状态）。

惊喜来了：数字 $6$ 竟然天生就满足了这个复杂的条件！它已经是 110 了！

这意味着我们省掉了从 100 凑出 110 的那些步骤。

这导出了一个递归公式：

对于二进制 1xxxx...，它的总步数 = (消除最高位需要的理论总步数) - (消除剩余部分 xxxx... 需要的步数)。

因为操作是可逆的，“从 A 到 B”的步数等于“从 B 到 A”的步数。本来我们需要花力气把后面凑成特定样子，现在它已经部分凑好了，所以是“减去”这部分工作量。

用公式验证 $n=6$ (110)：

最高位在第 2 位。理论总步数 = $2^{2+1} - 1 = 7$ 步。
剩下的部分是 10 (也就是 2)。
所以 $f(110) = 7 - f(10)$。
现在算 $f(10)$：最高位在第 1 位。理论总步数 = $2^{1+1} - 1 = 3$ 步。剩余部分是 0。
$f(10) = 3 - f(0) = 3 - 0 = 3$ 步。
回到最开始：$f(110) = 7 - 3 = 4$ 步。答案是对的！

再验证 $n=3$ (11)：

最高位在第 1 位。理论总步数 = $2^{1+1} - 1 = 3$ 步。
剩下的部分是 1。
$f(11) = 3 - f(1)$。
算 $f(1)$：理论总步数 $2^{0+1} - 1 = 1$ 步。
$f(11) = 3 - 1 = 2$ 步。答案也是对的

递归逻辑：

看到一个二进制数，找到它最高位的 1（假设是第 $k$ 位），它贡献的基础步数是 $2^{k+1}-1$。然后“减去”剩下那些位需要的步数。

具体代码

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        # 基础情况：如果是0，不需要操作
        if n == 0:
            return 0
        
        # 1. 找到最高位的 1 在哪里
        # 比如 n = 6 (110), 最高位是第 2 位 (从0开始数)
        k = 0
        while (1 << k) <= n:
            k += 1
        k -= 1  # 现在 1 << k 是不大于 n 的最大 2 的幂
        
        # 2. 套用公式：理论总步数 - 剩下的部分的步数
        # 理论总步数 = 2^(k+1) - 1
        # 剩下的部分 = n ^ (1 << k)  (即去掉最高位)
        return (1 << (k + 1)) - 1 - self.minimumOneBitOperations(n ^ (1 << k))

1611. 使整数变为 0 的最少操作次数

beautifulremi

题目

解题思路

具体代码