题目

类型：位运算

解题思路

目的是使得最终结果的二进制表示均为 0，两种操作对二进制数的影响分别为「整体右移」和「消减最低位的 1」。

因此整个模拟过程其实是：如果当前的 num 最低位不为 1（偶数），则不断进行右移，直到最低位为 1（奇数），然后再对最低位的 1 进行消减，直到二进制表示中的所有 1 均被消减完（结果为 0），模拟过程结束。

换句话说，总的操作次数为 = 右移次数 + 消减次数 ：

右移次数：num 中最高位 1 的所在的位置；
消减次数：num 中 1 的个数。

代码

class Solution {
    public int numberOfSteps(int num) {
        return Math.max(getLoc(num) + getCnt(num) - 1, 0);
    }
    int getLoc(int x) {
        for (int i = 31; i >= 0; i--) {
            if (((x >> i) & 1) == 1) return i + 1;
        }
        return -1; // never
    }
    int getCnt(int x) {
        int ans = 0;
        for (int i = 31; i >= 0; i--) {
            if (((x >> i) & 1) == 1) ans++;
        }
        return ans;
    }
}