1342. Number of Steps to Reduce a Number to Zero #
题目 #
给你一个非负整数 nums，返回将它变为 0 所需要的步数。
如果当前数字是偶数，则将它除以 2，否则减去 1。
思路 #
- 模拟
- 数学 + 位运算
- 可从如下角度考虑模拟过程:
- 若
nums最低位非1，则进行右移 - 若
nums最低位为1，则消减最低位的1
- 若
- 总操作次数等于: 最高位 1 的右移次数 +
nums的二进制表示中1的个数
- 可从如下角度考虑模拟过程:
代码 #
模拟 #
class Solution {
public int numberOfSteps(int num) {
int step = 0;
while (num != 0 && ++step > 0) num = (num & 1 == 0) ? num >> 1 : num - 1;
return step;
}
}
数学 + 位运算 #
class Solution {
public int numberOfSteps(int num) {
/** 定位最高位1的右移次数 */
int numShift = 0;
for (int i = 31; i >= 0; i--) {
if ( ((num >> i) & 1) == 0 ) continue;
numShift += 1;
break;
}
/** 计数num的二进制表示中1的个数 */
int numOnes = 0;
for (int i = 31; i >= 0; i--) {
if ( ((num >> i) & 1) == 0 ) continue;
numOnes += 1;
}
/** 将数字变为 0 的操作次数 等同于最高位1的右移次数 + 二进制表示中1的个数 */
return numShift + numOnes;
}
}