题目描述

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

示例 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：
输入：num = 8
输出：4
解释：
步骤 1） 8 是偶数，除以 2 得到 4 。
步骤 2） 4 是偶数，除以 2 得到 2 。
步骤 3） 2 是偶数，除以 2 得到 1 。
步骤 4） 1 是奇数，减 1 得到 0 。

示例 3：
输入：num = 123
输出：12

---

正确代码

    /**
     * 暴力解法
     * 数字想要变成0，最后两步一定是2变1，1变0
     * 而为了出现2，数字最后肯定是变化到3喝4两种情况
     * 我们只需要循环计算出之前变成3或4的步骤数加3即可
     * @author songbaicheng
     * @date 2022/1/31 10:52
     * @param num
     * @return int
     */
    public static int numberOfSteps01(int num) {
        if (num == 0) {
            return 0;
        }
        if (num == 1) {
            return 1;
        }
        if (num == 2) {
            return 2;
        }

        int step = 3;

        while (true) {
            if (num == 3 || num == 4) {
                break;
            }

            if (num % 2 == 0) {
                num /= 2;
            } else {
                num -= 1;
            }
            step++;
        }

        return step;
    }

    /**
     *  位运算
     *  将发生的情况都总结统一到一条公式当中
     *  我们只需要关心下一步的结果是不是0即可，只要不是就步骤加一
     *  这里用位运算来判断数字是否为奇数和进行除以2操作
     * @author songbaicheng
     * @date 2022/1/31 10:48
     * @param num 
     * @return int
     */
    public static int numberOfSteps02(int num) {
        int ret = 0;

        while (num > 0) {
            ret += (num > 1 ? 1 : 0) + (num & 0x01);
            num >>= 1;
        }

        return ret;
    }