Easy

题目描述

给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。

示例 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 。

示例 3：

输入：num = 123
输出：12

提示：

  • 0 <= num <= 10^6

解题思路

这道题有两种主要解法：模拟法和位操作法。

方法一：模拟法 直接按照题目要求模拟操作过程：如果当前数字是偶数就除以 2，如果是奇数就减 1，直到数字变成 0 为止，统计操作次数。这是最直观的方法，时间复杂度为 O(log n)。

方法二：位操作法（推荐） 观察操作规律可以发现，这个过程实际上是在处理数字的二进制表示：

  • 除以 2 相当于右移一位（去掉最低位）
  • 减 1 操作只有在最低位为 1（奇数）时才会进行

因此，操作总数等于：数字的二进制位数 + 二进制表示中 1 的个数 - 1。

  • 二进制位数对应右移操作的次数
  • 1 的个数对应减 1 操作的次数
  • 减 1 是因为最后一个 1 不需要减 1 操作就能变成 0

位操作法的时间复杂度也是 O(log n)，但常数更小，代码更简洁。

代码实现

class Solution {
public:
    int numberOfSteps(int num) {
        if (num == 0) return 0;
        
        int bits = 0;
        int ones = 0;
        int temp = num;
        
        while (temp > 0) {
            if (temp & 1) ones++;
            bits++;
            temp >>= 1;
        }
        
        return bits + ones - 1;
    }
};

class Solution:
    def numberOfSteps(self, num: int) -> int:
        if num == 0:
            return 0
        
        return num.bit_length() + bin(num).count('1') - 1

public class Solution {
    public int NumberOfSteps(int num) {
        if (num == 0) return 0;
        
        int bits = 0;
        int ones = 0;
        int temp = num;
        
        while (temp > 0) {
            if ((temp & 1) == 1) ones++;
            bits++;
            temp >>= 1;
        }
        
        return bits + ones - 1;
    }
}

var numberOfSteps = function(num) {
    let steps = 0;
    while (num > 0) {
        if (num % 2 === 0) {
            num = num / 2;
        } else {
            num = num - 1;
        }
        steps++;
    }
    return steps;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(log n)
空间复杂度O(1)

其中 n 是输入数字的值，时间复杂度取决于数字的二进制位数。

相关题目