Steps to Reduce a Number to Zero

Q: 将一个数字减小到零的时间复杂度是多少？

运行这个过程需要 O(log n) 时间，因为至少每隔一步，数量就会减半：当 n = 2^31 - 1 时，需要 61 步。使用内置的位指令统计二进制位数需要 O(1) 时间。

Q: 下面哪个小于 2^31 的数字需要最多步？

2^31 - 1 ，它的二进制表示由 31 个 1 组成。它需要进行 31 次减法和 30 次折半，总共 61 步。没有更小的数能同时拥有这么多位数和这么多个 1。

Q: 为什么减半等同于右移？

二进制数是若干个 2 的幂相加得到的。将一个偶数除以 2 ，会使每个幂次减 1，从而让每一位数字向右移动一位，并去掉末尾的 0 。这就是 n >> 1 的作用，因此你可以用任意一种方式表示除以 2。

入门位运算数学与模拟

+10

从一个非负整数 n 开始，重复应用以下规则，直到它变为 0：如果这个数是偶数，就将它除以 2；如果是奇数，就减去 1。每应用一次规则算作一步。返回所需的步数。

函数

numberOfSteps(n: integer) → integer

ninteger: 起始数字
返回值integer: 直到数字变为 0 所需的步数

约束条件

0 ≤ n ≤ 2³¹ - 1

示例

输入: n = 14
输出: 6
解释: 这个数字按 14 → 7 → 6 → 3 → 2 → 1 → 0 变化：除以 2 三次，再减去 3 次，共 6 步。

输入: n = 8
输出: 4
解释: 8 → 4 → 2 → 1 → 0。2 的幂减半 3 次，最后还需要减 1 次，共 4 步。

输入: n = 123
输出: 12
解释: 123 的二进制表示是 1111011：共 7 位，其中有 6 个 1。这 6 个 1 需要 6 次减法，最高位 1 以下的 6 位需要 6 次除以 2，共需 12 步。

进阶

假设奇数也可以加 1。到达 0 最少需要几步？对于 15，哪种选择是正确的？

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

在二进制中，除以 2 会去掉最后一位数字，而从奇数中减去 1 会把末尾的 1 变成 0。因此，对于 n > 0，答案是二进制位数加上 1 的个数，再减去 1。直接执行这个规则也很快：最多需要 61 步。

运行该流程

思路

运行这个规则并统计步数。对于 14，循环会依次经过 7、6、3、2、1 和 0：共 6 步。

减法总是会让奇数变成偶数，因此至少每两步就会有一次减半。小于 2^31 的数在达到 1 之前，最多减半 30 次。每次减半前减一次，最后再减一次，循环最多运行 61 次。当 n = 0 时，循环不会运行，答案是 0。

算法

将 steps 设为 0。
当 n > 0 时：如果 n 是偶数，就将 n 设为 n / 2，否则设为 n-1。
每次都给 steps 加上 1。
返回 steps。

def numberOfSteps(n):
    steps = 0
    while n > 0:
        if n % 2 == 0:
            n //= 2
        else:
            n -= 1
        steps += 1
    return steps

二进制位数

思路

每一步都会去掉最后一位二进制数字，或者把末尾的 1 变成 0。14 是 1110：除以 2 得到 111，从 111 中减去 1 得到 110。每个 1 都必须清除一次，因此每个 1 都要减去一次。每位数字都必须去掉，每次除以 2，除了最前面的 1：当只剩下 1 时，减去 1 就会得到 0。所以答案是 length - 1 + ones，对于 14，结果是 4 - 1 + 3 = 6。

Java、C、C++、Go、Rust 和 Swift 都内置了用于计算这两种数量（前导零和置位）的功能，在大多数处理器上会编译成单条指令。其他语言可以在最多 31 轮的循环中用 % 2 读取各位数字。先处理 n = 0：它没有 1 位可用于确定公式。

算法

如果 n == 0，返回 0。
找出 length，也就是 n 的二进制位数。
找出 ones，也就是值为 1 的位数。
返回 length - 1 + ones。

def numberOfSteps(n):
    if n == 0:
        return 0
    # Every bit below the leading one costs a halving,
    # and every 1 bit costs a subtraction.
    return n.bit_length() - 1 + bin(n).count("1")

易错点和边界情况

在位公式中忘记了 n = 0。length - 1 + ones 会得到 -1，而前导零计数为 0 时可能未定义（在 C 中为 __builtin_clz(0)）。
把最高位也算作一次减半。通过减法，1 会变成 0，所以 8 = 1000 需要 4 - 1 + 1 = 4 步，而不是 5 步。
对奇数写 n = (n-1) / 2 并只计一步。这一行实际上执行了两步，因此 14 的结果是 4，而不是 6。
在 n > 1 时循环。这会在最后一步之前停止，而最后一步会把 1 变成 0。

常见问题3

将一个数字减小到零的时间复杂度是多少？

运行这个过程需要 O(log n) 时间，因为至少每隔一步，数量就会减半：当 n = 2^31 - 1 时，需要 61 步。使用内置的位指令统计二进制位数需要 O(1) 时间。

下面哪个小于 2^31 的数字需要最多步？

2^31 - 1，它的二进制表示由 31 个 1 组成。它需要进行 31 次减法和 30 次折半，总共 61 步。没有更小的数能同时拥有这么多位数和这么多个 1。

为什么减半等同于右移？

二进制数是若干个 2 的幂相加得到的。将一个偶数除以 2，会使每个幂次减 1，从而让每一位数字向右移动一位，并去掉末尾的 0。这就是 n >> 1 的作用，因此你可以用任意一种方式表示除以 2。

def numberOfSteps(n):
    # 在这里编写代码

测试 #1

测试 #2

测试 #3

参数

n = 14

预期输出