题目描述

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

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

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

样例

输入：n = 0
输出：0

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

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

输入：n = 9
输出：14

输入：n = 333
输出：393

限制

• 0 <= n <= 10^9

算法

(找规律) $O(\log n)$

1. 考虑一种简单的情况，假设 $n$ 是 2 的幂次，此时需要 $2n-1$ 次操作。
2. 现在 $n$ 是任意一个整数，但他可以用若干个 2 的幂次来表示。我们用递归来描述整个求解过程 $solve(n)$：
   • 假设 $m$ 是不超过 $n$ 的最大的 2 的幂次，则答案为 $2m - solve(n-m) - 1$。
   • 这里是先将 $m$ 清零，但 $m$ 清零的过程中，一定会变到 $n$，所以清零 $n-m$ 的这些步骤可以省去，去递归求解。
3. 整个过程可以变成非递归的。

时间复杂度

• 共 $O(\log n)$ 个二进制位，所以时间复杂度为 $O(\log n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int minimumOneBitOperations(int n) {
        int ans = 0;
        for (int i = 0; i < 30; i++)
            if (n & (1 << i))
                ans = (1 << (i+1)) - ans - 1;

        return ans;
    }
};