Difficulty: Easy

Related Topics: Bit Manipulation

Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

Example 1:

  1. Input: num = 14
  2. Output: 6
  3. Explanation: 
  4. Step 1) 14 is even; divide by 2 and obtain 7. 
  5. Step 2) 7 is odd; subtract 1 and obtain 6.
  6. Step 3) 6 is even; divide by 2 and obtain 3. 
  7. Step 4) 3 is odd; subtract 1 and obtain 2. 
  8. Step 5) 2 is even; divide by 2 and obtain 1. 
  9. 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 <= 10^6

Solution

Language: Java

// 递归
class Solution {    
    // 解题技巧
    // 使用 & 来判断奇偶 
    //   - 偶数的最后一位 bit 是 0
    //   - 奇数的最后一位 bit 是 1
    //   - 通过 & 1 操作可以拿到最后一位 bit
    // 使用 >> 来实现除 2 操作
    public int numberOfSteps (int num) {
        if (num == 0) return 0;

        if ((num & 1) == 1) {
            return numberOfSteps(num - 1) + 1;
        } else {
            return numberOfSteps(num >> 1) + 1;
        }
    }
}

// 遍历
class Solution {
    public int numberOfSteps (int num) {
        int step = 0;

        while (num > 0) {
            // odd
            if ((num & 1) == 1) {
                num = num - 1;
            } else {
                num = num >> 1;
            }
            step++;
        }

        return step;
    }
}

// 位运算
class Solution {

    // 两个操作
    // 1. 遇到奇数【减1】
    // 2. 遇到偶数【除2】
    // 那我们先来看看遇到偶数的次数如何计算
    // 举个例子 8 (1000)
    // 8 >> 1  =>  4 (0100)
    // 4 >> 1  =>  2 (0010)
    // 2 >> 1  =>  1 (0001)
    //
    // 对于 8 这个偶数来说，我们需要除三次才能将它变成奇数
    // 那么这个 3 是如何计算出来的呢？
    // 就是这个数的二进制数长度 - 1，为什么？
    // 因为一个 n 位长二进制数，经过 n - 1 次右移运算，最后一定是 1 
    // 
    //
    // 在看一个例子 12 (1100)
    // 12 >> 1  =>  6 (0110)
    // 6  >> 1  =>  3 (0011) <- 出现奇数【减一】
    // 3  -  1  =>  2 (0010)
    // 2  >> 1  =>  1 (0001) <- 出现奇数【减一】
    // 1  -  1  =>  0 (0000)
    // 总共的操作次数是 5 次
    // 偶数的操作次数是 bitLen(12) - 1 
    // 奇数的操作次数是 bitCount(12)
    public int numberOfSteps (int num) {
        // 需要处理一下 0 的情况
        if (num == 0) return 0;

        return bitLen(num) - 1 + Integer.bitCount(num);
    }

    private int bitLen(int num) {
        return 32 - Integer.numberOfLeadingZeros(num);
    }
}