题目重点：从 Salesforce SMTS OA 的 1≤n<2^60 完整题意出发，把操作转成最少非零位的有符号二进制表示，解释 mod 4 贪心与边界，并用独立枚举对照。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- i 是任意非负整数，允许临时超过初始 n 或变成负数；题目只说加减 2^i、最终为 0，未限制中间值。
- 计数每次加/减一个幂为一步，乘除 2 是算法分析中的位移而非实际允许的操作。
- 输入必须为正整数且小于 2^60；Python 示例校验正值，位宽上限由题面而非函数硬编码。
解题路线
- 把从 n 到 0 的操作反向看：n 是若干个带正负号的 2 的幂之和，最少步数就是求有符号二进制表示的最少非零位。相同幂两次同号可合并成更高位，异号可抵消，因此最优解可规整为每位至多一个 ±1。
- 逐位从低到高处理。n 为偶数时最低位必须为 0，右移即可；n 为奇数时最低位必须选 +1 或 -1。若 n mod 4=1，选 +1，使剩余 `(n-1)/2` 为偶数；若 n mod 4=3，选 -1，使 `(n+1)/2` 为偶数。n=1 时直接选 +1 结束。每选一次非零位计一步。
- 这种选法产生非相邻形式（NAF）：非零位后紧跟的高一位为 0。局部连续的同号普通二进制位可由 `2^k-1` 形式压缩，高位进位后非零位数不增加；标准 NAF 在所有 ±1/0 的二进制表示中非零位数最少。可用小数全枚举验证。
手动走一遍
n=15 二进制 1111，逐个减 8、4、2、1 要 4 步；有符号写作 16−1，只需先 +1 到 16，再 −16 到 0，共 2 步。n=10=8+2，答案 2。n=1 直接减 1，答案 1。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def min_power_of_two_operations(n: int) -> int:
"""Minimum count of signed powers of two summing to positive n."""
if n <= 0:
raise ValueError("n must be positive")
operations = 0
while n:
if n & 1:
digit = 1 if n == 1 or n % 4 == 1 else -1
n -= digit
operations += 1
n //= 2
return operations
复杂度
循环每次至少右移一位，偶尔加 1 产生进位，时间 O(log n)、额外空间 O(1)。n<2^60 时循环次数不超过约 61 位；大整数语言也要注意 n+1 的位宽。
易错点与追问
容易失分的边界
- 只按普通二进制 popcount 算，例如 15 会错误得 4。
- 把算法里的右移当作实际免费操作；它只是逐位求表示，实际每个非零位仍对应一步。
- 奇数都做 n−1，错过 2^k−1 的进位压缩。
- 对 n=1 盲目按 n mod 4 之外的规则选进位，陷入循环。
- 无依据地禁止中间值超过初始 n，15→16→0 就会被排除。
继续深挖
- 若只允许减 2^i，不允许加，答案如何变化？
- 若每个 i 只能使用一次，这种表示仍可行吗？
- 如何输出一条最优加减操作序列，而不只返回步数？
- 在固定 64 位整数语言里 n 接近上界时如何避免进位溢出？
