Force buckle 6_ 1342. Number of operations to change a number to 0

Give you a nonnegative integer num , Please go back and turn it into 0 The number of steps required . If the current number is even , You need to divide it by 2 ; otherwise , subtract 1 .

Example 1：

 Input ：num = 14
 Output ：6
 explain ：
 step  1) 14  It's even , Divide  2  obtain  7 .
 step  2） 7  Is odd , reduce  1  obtain  6 .
 step  3） 6  It's even , Divide  2  obtain  3 .
 step  4） 3  Is odd , reduce  1  obtain  2 .
 step  5） 2  It's even , Divide  2  obtain  1 .
 step  6） 1  Is odd , reduce  1  obtain  0 .

Example 2：

 Input ：num = 8
 Output ：4
 explain ：
 step  1） 8  It's even , Divide  2  obtain  4 .
 step  2） 4  It's even , Divide  2  obtain  2 .
 step  3） 2  It's even , Divide  2  obtain  1 .
 step  4） 1  Is odd , reduce  1  obtain  0 .

Example 3：

 Input ：num = 123
 Output ：12

source ： Power button （LeetCode）

The principles used in both solutions are based on the characteristics of binary numbers , According to the 0 or 1 Determine the corresponding number of steps .

Java solution

class Solution {
    
    public int numberOfSteps(int num) {
    
        int ret = 0;
        while (num > 0) {
    
            ret += (num > 1 ? 1 : 0) + (num & 0x01);
            // take & The numbers on both sides of the symbol are converted into binary , To perform bitwise operations 
            num >>= 1;
        }
        return ret;
    }
}

Python solution

class Solution:
    def numberOfSteps(self, num: int) -> int:
        ans = 0
        while num:
            ans += num & 1
            if num > 1:
                ans += 1
            num >>= 1
        return ans