Leecode刷题 1342. 将数字变成 0 的操作次数

题目：

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

思路：

初解思路

思路很简单，就是通过最后一位判断奇偶，然后分别进行相应的运算

int numberOfSteps(int num){
    int step = 0;
    while(num != 0)
    {
        if(num&0x01)//是奇数
            num -= 1;
        else
            num /= 2;
        step++;
    }
    return step;
}
1
2
3
4
5
6
7
8
9
10
11
12

官方思路 方法一：模拟

将 num 与 1 进行位运算来判断 num 的奇偶性。

记录操作次数时：
如果 num是奇数，我们需要加上一次减 1 的操作。
如果num > 1，我们需要加上一次除以 2 的操作。
然后使 num 的值变成 num/2。
重复以上操作直到num=0 时结束操作。

这里的一个点就是，通过判断是奇数之后，直接次数加一即可，因为除以2的操作，使得这个奇数与他减去1之后偶数/2的结果是相同的。

复杂度分析

时间复杂度：O(log num)，其中 num 是输入数值。每次循环都将 num 的数值减半，因此时间复杂度为 O(log num)。

空间复杂度：O(1)。只需要常数空间。

int numberOfSteps(int num){
    int step = 0;
    while(num)
    {
       step += (num > 1 ? 1 : 0) + (num & 0x01);
       num >>= 1; 
    }
    return step;
}
1
2
3
4
5
6
7
8
9

官方思路 方法二：直接计算

算法-求一个二进制数的长度
由方法一的步骤可知，当 num>0 时，总操作次数等于总减 1 的操作数与总除以 2 的操作数之和。总减 1的操作数等于 num 二进制位 1 的个数，总除以2 的操作数等于 num 二进制数长度减 1，即最高位右移到最低位的距离。
先举几个例子解释一下什么是二进制数的长度，比如8 = 1000，则长度是4， 7 = 0111，长度为3。所以一个二进制数的长度也即最高位1的下标值+1（下标从0开始）。
二进制数长度len 可以通过前导零数目 clz 间接求解，即 len=W−clz，其中 W=32 是 int 类型的位数。

使用二分法加速求解前导零数目，算法如下：
首先判断 num 前半部分是否全为零，如果是，则将clz 加上前半部分的长度，然后将后半部分作为处理对象，否则将前半部分作为处理对象。重复以上操作直到处理的对象长度为 1，直接判断是否有零，有则将clz 加 1。

使用分治法来加速求解二进制数位 11 的个数，算法如下：
对二进制数num，它的位 1的个数等于所有位的值相加的结果，比如 110110101 (2) =1+0+1+1+0+1+0+1。我们可以将 8 个位的求和分解成 4 个相邻的位的求和，然后将 4 个中间结果分解成 2 个相邻的求和，即 10110101 (2) =(1+0)+(1+1)+(0+1)+(0+1)=((1+0)+(1+1))+((0+1)+(0+1))=5。32 位数的求解过程同理。

int length(uint num)//必须用uint才能不溢出
{
    int clz;
    if((num>>16) == 0)
    {
        clz += 16;
        num <<= 16;//上面并没有改变num值，只是移位之后做了判断。此处是如果前16位均为0，则判断后16位
    }
    if((num >> 24) == 0)
    {
        clz += 8;
        num <<= 8;
    }
    if((num >> 28) == 0)
    {
        clz += 4;
        num <<= 4;
    }
    if((num >> 30) == 0)
    {
        clz += 2;
        num <<= 2;
    }
    if((num >> 31) == 0)
    {
        clz += 1;
        num <<= 1;
    }
    return 32 - clz;
} 

int count(int num)
{
    num = (num & 0x55555555) + ((num>>1) & 0x55555555);
    num = (num & 0x33333333) + ((num>>2) & 0x33333333);
    num = (num & 0x0F0F0F0F) + ((num>>4) & 0x0F0F0F0F);
    num = (num & 0x00FF00FF) + ((num>>8) & 0x00FF00FF);
    num = (num & 0x0000FFFF) + ((num>>16) & 0x0000FFFF);
    return num;
}

int numberOfSteps(int num){
    return (num == 0) ? 0 : length(num) - 1 + count(num);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44