原文链接: https://leetcode-cn.com/problems/number-of-steps-to-reduce-a-number-to-zero

英文原文

Given an integer num, return the number of steps to reduce it to zero.

In one step, if the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

 

Example 1:

Input: num = 14
Output: 6
Explanation: 
Step 1) 14 is even; divide by 2 and obtain 7. 
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3. 
Step 4) 3 is odd; subtract 1 and obtain 2. 
Step 5) 2 is even; divide by 2 and obtain 1. 
Step 6) 1 is odd; subtract 1 and obtain 0.

Example 2:

Input: num = 8
Output: 4
Explanation: 
Step 1) 8 is even; divide by 2 and obtain 4. 
Step 2) 4 is even; divide by 2 and obtain 2. 
Step 3) 2 is even; divide by 2 and obtain 1. 
Step 4) 1 is odd; subtract 1 and obtain 0.

Example 3:

Input: num = 123
Output: 12

 

Constraints:

• 0 <= num <= 106

中文题目

给你一个非负整数 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

通过代码

高赞题解

解题思路

以32位二进制为例, 例如15(0x0000000f):

1. 遇奇减1, 即将末位1变为0, 和0xfffffffe(-2)取&即可;
2. 遇偶除2, 即右移一位即可;
3. 两种情况都需要次数加1.

迭代

class Solution {
    public int numberOfSteps (int num) {
        int count = 0;
        while (num != 0) {
            count++;
            num = (num & 1) == 1 ? num & -2 : num >> 1;
        }
        return count;
    }
}

递归

class Solution {

    private int count = 0;

    public int numberOfSteps (int num) {
        if (num != 0) {
            count++;
            if ((num & 1) != 0) {
                numberOfSteps(num & -2);
            } else {
                numberOfSteps(num >> 1);
            }
        }
        return count;
    }
}

Tips

其实对于count的自增操作, 也可以转变为count + 1, 按照371.两整数之和的思路, 让代码只存在位运算和逻辑运算.

统计信息

通过次数	提交次数	AC比率
42933	52423	81.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言