Uber OA 整数归零：最少 ±2 的幂次操作

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 输入非负整数 n；一次操作选择任意 i≥0，让当前整数加上或减去 2^i，目标达到 0，最小化操作次数。
• 中间值可大于初始 n（如 n=7 可加 1 到 8 再减 8）；不能用‘绝不超出 n’剪掉最优解。
• 不限制 i 的最大值；Python 整数可任意精度，代码返回操作次数而不返回具体幂次序列。

解题路线

1. 每次 ±2^i 等价于把 n 表示成若干带正负号的二进制幂之和，目标是尽可能少的非零系数。
2. 从最低位处理：n 为偶数时，当前位系数为 0，直接右移；n 为奇数时必须在当前位选 +1 或 −1 并计一次。
3. 若 n≡1 (mod 4)，取 n−1 后右移产生更多连续零位；若 n≡3 (mod 4)，取 n+1 后右移。n=1 直接减 1。该规则构造最小非零位数的带符号二进制表示。

手动走一遍

n=7（二进制 111）可先加 1 得 8，再减 8 得 0，共 2 步；若只按置位数减去 4、2、1，会需 3 步。n=10（二进制 1010）需减 8、减 2，共 2 步。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Minimum +/- power-of-two operations using signed binary digits."""


def minimum_operations_to_zero(n: int) -> int:
    if n < 0:
        raise ValueError("n must be nonnegative")
    operations = 0
    while n:
        if n % 2 == 0:
            n //= 2
        else:
            operations += 1
            if n == 1 or n % 4 == 1:
                n = (n - 1) // 2
            else:
                n = (n + 1) // 2
    return operations

复杂度

每轮右移至少一位，进位最多使有效位数增加一位，时间 O(log n)、额外空间 O(1)（按机器整数计；任意精度整数运算本身随位数增长）。

易错点与追问

容易失分的边界

• 把答案直接等同普通 popcount 会漏掉 7=8−1 这类进位更优的情况。
• 奇数 n=1 必须结束，若机械按 n%4 选方向仍会选减 1，但显式处理更清楚。
• 某汇编帖的伪代码在奇数分支只做 n+=1 而不立刻右移，虽仍可继续循环，但逐位推导时要明确下一轮如何推进位次。

继续深挖

• 若还要返回实际操作，每个奇数位记录当前位次及选择的 ±2^i，再反向检查它们的代数和等于 n。
• 若只允许减法，答案退化为 popcount(n)；若操作幂次受上限约束，则当前贪心不一定适用。