LogicStack-LeetCode 精讲：1342. 将数字变成 0 的操作次数——模拟与二进制位运算双解法

教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载导读本文基于「宫水三叶的刷题日记」刷穿 LeetCode 系列中 1342. 将数字变成 0 的操作次数简单 一题展开系统拆解「按奇偶性迭代模拟」与「二进制位运算直接计数」两种思路。读完本文你将掌握如何用循环模拟规则直至归零、如何从二进制视角把操作次数分解为「右移次数 消减次数」、以及lowbit等位运算技巧在计数类题目中的典型应用并能够对照仓库中的多语言参考代码独立实现与验证。一、题目解读与数据范围题目给出一个非负整数num要求返回把它变成0所需要的步数。每一步的操作规则只有两条当前数字是偶数把它除以2当前数字是奇数把它减去1。数据范围约束为0 num 10^6这是一个典型的简单模拟题Tag 为「模拟」、「数学」。在仓库的 模拟 索引中本题被收录为推荐指数 的模拟类题目同时由于解法二引入了大量位运算思想它也出现在 位运算 分类体系中。需要特别注意的边界情况是num 0此时不需要任何操作答案应为0。二、示例推演示例 1num 14期望输出6步骤当前值奇偶性操作结果114偶数除以 2727奇数减 1636偶数除以 2343奇数减 1252偶数除以 2161奇数减 10共 6 步得到答案6。示例 2num 8期望输出48 → 4 → 2 → 1 → 0过程为8 / 2 4、4 / 2 2、2 / 2 1、1 - 1 0共 4 步。示例 3num 123期望输出12可自行按规则推演验证答案与模拟结果一致。三、解法一按规则循环模拟3.1 核心思路最直观的解法就是忠实翻译题意循环判断当前num的奇偶性偶数除以2奇数减1每执行一次操作计数器ans加一直到num变为0时返回ans。由于每轮操作至少让数值减半偶数直接除以 2奇数减 1 后变成偶数、下一轮再除以 2循环轮数被严格限制在O(log num)量级性能完全足够。3.2 Java 实现class Solution { public int numberOfSteps(int num) { int ans 0; while (num ! 0 ans 0) num num % 2 0 ? num / 2 : num - 1; return ans; } }3.3 C 实现class Solution { public: int numberOfSteps(int num) { int ans 0; while (num ! 0 ans 0) num (num % 2 0) ? num / 2 : num - 1; return ans; } };3.4 Python 实现class Solution: def numberOfSteps(self, num: int) - int: ans 0 while num ! 0: ans 1 num num // 2 if num % 2 0 else num - 1 return ans3.5 复杂度分析时间复杂度O(log num)。每次循环num至少减半奇数先减 1 再于下轮除以 210^6级别的输入最多约 20 轮。空间复杂度O(1)仅使用常数个变量。3.6 实现细节说明循环条件写成num ! 0天然覆盖num 0时答案为0的边界情况Java/C 版本中 ans 0是一种计数技巧只要进入循环体就自增计数同时借助短路求值保证num 0时不进入循环Python 版本拆开了计数与更新两步逻辑更直白三份代码语义完全等价。四、解法二从二进制性质直接计算4.1 两种操作在二进制下的含义把num看作二进制表示后两种操作的位级意义变得非常清晰除以 2偶数等价于二进制整体右移一位丢弃最低位减去 1奇数等价于消减最低位的 1最低位为 1 时减 1该位变为 0。因此整个模拟过程的本质是如果当前二进制最低位不为 1偶数则不断右移直到最低位为 1奇数然后消减最低位的 1直到二进制表示中的所有 1 都被消减完结果为 0过程结束。由此可以导出总操作次数的精确分解总操作次数 右移次数 消减次数右移次数num中最高位 1 所在的位置从 1 开始计数减 1。除最高位的 1 本身外其余低位每一层至少需要一次右移来推进处理消减次数num二进制表示中1 的个数。每个 1含最高位的 1都需要一次「减 1」操作消掉。两者相加即得ans getLoc(num) getCnt(num) - 1其中getLoc求最高位 1 的位置getCnt求 1 的个数。由于num 0时不存在最高位外层用Math.max(..., 0)兜底。4.2 公式验证以num 14为例14 (1110)₂最高位 1 位于第 4 位即getLoc(14) 4二进制中共有 3 个 1即getCnt(14) 3代入公式4 3 - 1 6与模拟结果一致。✓4.3 基础实现逐位扫描getLoc从高到低扫描 32 个二进制位找到第一个为 1 的位getCnt逐位统计 1 的个数。Java 实现class Solution { public int numberOfSteps(int num) { return Math.max(getLoc(num) getCnt(num) - 1, 0); } int getLoc(int x) { for (int i 31; i 0; i--) { if (((x i) 1) 1) return i 1; } return -1; // never } int getCnt(int x) { int ans 0; for (int i 31; i 0; i--) { if (((x i) 1) 1) ans; } return ans; } }4.4 优化实现用 lowbit 统计 1 的个数逐位扫描仍会对大量为 0 的高位做无用功。这里可以引入lowbit技巧lowbit(x) x -x能在O(1)内取出x二进制表示中最低位 1 所代表的数值。每次用x - (x -x)即可直接抹掉一个最低位的 1循环次数等于 1 的个数。Java 实现class Solution { public int numberOfSteps(int num) { return Math.max(getLoc(num) getCnt(num) - 1, 0); } int getLoc(int x) { for (int i 31; i 0; i--) { if (((x i) 1) 1) return i 1; } return -1; // never } int getCnt(int x) { int ans 0; while (x ! 0 ans 0) x - (x -x); // lowbit return ans; } }C 实现class Solution { public: int getLoc(int x) { for (int i 31; i 0; i--) { if ((x i) 1) return i 1; } return -1; } int getCnt(int x) { int ans 0; while (x ! 0 ans 0) x - (x -x); return ans; } int numberOfSteps(int num) { return max(getLoc(num) getCnt(num) - 1, 0); } };Python 实现class Solution: def getLoc(self, x: int) - int: for i in reversed(range(32)): if (x i) 1: return i 1 return -1 def getCnt(self, x: int) - int: ans 0 while x: x - (x -x) ans 1 return ans def numberOfSteps(self, num: int) - int: return max(self.getLoc(num) self.getCnt(num) - 1, 0)4.5 复杂度分析时间复杂度O(C)其中C为int二进制表示的最大长度固定 32 位。getLoc至多扫描 32 位使用lowbit的getCnt循环次数等于 1 的个数同样不超过C。空间复杂度O(1)。4.6 位运算思路的仓库佐证lowbit(x) x -x与「统计二进制中 1 的个数」是位运算分类下的高频考点本仓库中有多处可对照的参考实现剑指 Offer 15. 二进制中1的个数简单 提供了「位数检查」「右移统计」「lowbit 解法」「分组统计」四种递进思路其中lowbit解法与本节的getCnt实现完全同构for (int i n; i ! 0; i - lowbit(i)) ans可互为印证191. 位1的个数简单 同样围绕二进制置位计数展开位运算 索引将 191、190、231、342、371、405、461 等题归入统一分类便于横向对比位运算技巧的通用模式。从源码结构可以推断本题解法二的本质是把「模拟过程」重述为「二进制串从最高位 1 到最低位逐层右移、逐 1 消减」的位级过程因此lowbit这类在位级层面直接命中 1的工具天然适配此类计数问题。五、两种解法对比与选型建议维度解法一循环模拟解法二二进制公式思路来源直接翻译题意易于理解需要先抽象出二进制规律时间复杂度O(log num)O(32)常数级空间复杂度O(1)O(1)代码简洁度极简35 行需额外实现getLoc/getCnt边界处理num 0天然跳过循环需max(..., 0)兜底适用场景面试首选思路最稳位运算专题训练深化二进制直觉对于num 10^6的数据范围两种解法的实际性能差异可以忽略不计。实战中推荐优先写出模拟解法保证正确性若目标是训练位运算能力再以解法二的推导过程作为深入理解的切入点。六、总结本题虽为「简单」难度却同时覆盖了两类核心能力模拟题的通法忠实翻译操作规则、维护计数器、正确处理边界num 0这在仓库 模拟 索引下的众多题目如 66. 加一、1486. 数组异或操作 等中一脉相承位运算的抽象能力把「除以 2 / 减 1」映射为「右移 / 消减最低位 1」进而导出总次数 最高位位置 1 的个数 - 1的闭式公式配合lowbit高效计数与 剑指 Offer 15. 二进制中1的个数简单 形成完整知识闭环。建议读者在本地分别实现模拟与位运算两版代码并用示例 1、2、3 以及边界值0、1逐一验证输出最终达到见题能写模拟、懂位能推公式的双重掌握。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LogicStack-LeetCode 题解精讲整数转罗马数字的贪心模拟解法LeetCode 12 中等LogicStack LeetCode 题解精讲整数转罗马数字的贪心模拟解法LeetCode 12 中等 本文以「宫水三叶的刷题日记」刷穿 LeetCod教程文档AlgoNote 算法通关手册LeetCode 137「只出现一次的数字 II」哈希表与位运算双解法精讲AlgoNote 算法通关手册LeetCode 137「只出现一次的数字 II」哈希表与位运算双解法精讲 本篇题解围绕「算法通关手册」AlgoNote中的教程文档知识库Moto 中 Amazon QuickSight 服务的模拟实现已支持 API、数据模型与实战用法Moto 中 Amazon QuickSight 服务的模拟实现已支持 API、数据模型与实战用法 导读 本文基于 Moto 开源仓库中的 quicksigh教程文档上一篇xxHash3的秘密推导从种子到派生密钥的安全处理下一篇OpenCut 新手指南如何快速跑通这款免费开源视频编辑器创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考