题目
给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 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 ；否则，减去 1 。
思路
如何判断是偶数还是奇数 %2==0
奇数和偶数 /2 -1都是位运算
/2 num»1
-1 num^1
循环解法
直接循环+逻辑
非循环位算法
总结规律
要为0 即将偶数部分和奇数部分清空
比如23 10111
奇数部分 将末尾1清空 23-22 10110
偶数部分 /2 右移1位 22-11 01011
奇数部分要把末尾1清空需要3次
偶数部分要移动5位才能位空 总共8次
解答
循环解法
class Solution {
public int numberOfSteps(int num) {
int step = 0;
while(num!=0){
if(num%2==0){
num = num/2;
}else{
num -= 1;
}
step++;
}
return step;
}
}
位运算
1的二进制位数-1 为出现单数的可能 为什么-1 因为最后的1可以纳入长度 由移位进行 return bin(num).count(‘1’) + num.bit_length() - 1
时空复杂度分析
如果采用循环解法 时间复杂度为O(n) 空间复杂度为O(1) 没有用到辅助空间
如果采用位激发 时间复杂度为O(1) 空间复杂度为O(1) 没有用到辅助空间
结语
采用位运算 二进制的特性 总结规律 能帮助我们好的解决问题 像android也有一些位运算能帮助解决问题
要牢记这两者的关系
