---

1342. 将数字变成 0 的操作次数

• 标签：位运算、数学
• 难度：简单

题目链接

• 1342. 将数字变成 0 的操作次数 - 力扣

题目大意

描述：给定一个非负整数 $num$。重复以下操作直到数字变为 $0$：

• 如果当前数字是偶数，将其除以 $2$。
• 如果当前数字是奇数，将其减去 $1$。

要求：返回将 $num$ 变为 $0$ 所需要的操作次数。

说明：

• $0 \le num \le 10^6$。

示例：

• 示例 1：

输入：num = 14
输出：6
解释：
步骤 1) 14 是偶数，除以 2 得到 7 。
步骤 2） 7 是奇数，减 1 得到 6 。
步骤 3） 6 是偶数，除以 2 得到 3 。
步骤 4） 3 是奇数，减 1 得到 2 。
步骤 5） 2 是偶数，除以 2 得到 1 。
步骤 6） 1 是奇数，减 1 得到 0 。

• 示例 2：

输入：num = 8
输出：4
解释：
步骤 1） 8 是偶数，除以 2 得到 4 。
步骤 2） 4 是偶数，除以 2 得到 2 。
步骤 3） 2 是偶数，除以 2 得到 1 。
步骤 4） 1 是奇数，减 1 得到 0 。

解题思路

思路 1：模拟

1. 核心思想

按照题目描述直接模拟即可。因为每步操作要么除以 $2$，要么减去 $1$，数字规模 $\le 10^6$，最多操作几十次，模拟效率很高。

2. 具体步骤

第 1 步：初始化 $steps = 0$。

第 2 步：当 $num > 0$ 时循环：

• 如果 $num$ 是偶数，$num //= 2$
• 如果 $num$ 是奇数，$num -= 1$
• $steps += 1$

第 3 步：返回 $steps$。

3. 举例说明

以 $num = 14$ 为例：

步骤	num	操作	steps
0	14	初始	0
1	7	14/2	1
2	6	7-1	2
3	3	6/2	3
4	2	3-1	4
5	1	2/2	5
6	0	1-1	6

结果为 $6$。

思路 1：代码

class Solution:
    def numberOfSteps(self, num: int) -> int:
        steps = 0
        while num:
            if num % 2 == 0:
                num //= 2
            else:
                num -= 1
            steps += 1
        return steps

思路 1：复杂度分析

• 时间复杂度：$O(\log num)$，每次操作至少让数字减半或减一，最多 $O(\log num)$ 次。
• 空间复杂度：$O(1)$。

---

思路 2：位运算分析

1. 核心思想

观察二进制表示可以发现规律。对于 $num$ 的二进制表示：

• 减 $1$ 操作将最低位的 $1$ 变成 $0$（奇数时发生）
• 除以 $2$ 操作右移一位（偶数时发生）

总操作次数 = 二进制中 $1$ 的个数（减 $1$ 操作次数）+ 二进制位数减 $1$（除以 $2$ 操作次数）。

特例：$num = 0$ 时操作次数为 $0$。

2. 思路 2：代码

class Solution:
    def numberOfSteps(self, num: int) -> int:
        if num == 0:
            return 0
        # 二进制中 1 的个数（减 1 操作次数）
        ones = bin(num).count('1')
        # 二进制位数减 1（除以 2 操作次数）
        bits = num.bit_length() - 1
        return ones + bits

3. 思路 2：复杂度分析

• 时间复杂度：$O(1)$，位运算直接计算。
• 空间复杂度：$O(1)$。

---

思路 3：对比与总结

思路	代码长度	效率	理解难度
模拟	5 行	$O(\log n)$	直观
位运算	3 行	$O(1)$	需理解二进制

两种方法都可以通过本题，模拟法更加直观易懂。