将整数减少到零需要的最少操作数 图解题解

每次加减一个 2 的幂，怎样最快把 n 清零

给一个正整数 n，每次操作给它加上或减去一个 2 的幂——1、2、4、8 这些 2 自乘出来的数，问最少几次能把 n 变成 0。题面例子：39 加 1 到 40、减 8 到 32、再减 32 到 0，3 步；54 也是 3 步。

39 的二进制有 4 个 1，答案为什么不是 4

39 的二进制是 100111。二进制就是只用 0 和 1 记数，每一位分量从右往左依次是 1、2、4、8、16、32，最右那头叫低位；100111 里四个 1 的分量 32、4、2、1 正好凑成 39。

看着很对的答案：四个 1 各减自己那份要 4 次，可题面只要 3 次。差在低三位 111：逐个减要 3 次，而加 1 让整串逢二进一、一次归零，这一步叫进位。

一串连续的 1，为什么加一次比逐个减省

给两种手段各记个账。连续的 1 长度为 k：逐个减花 k 次；给最低位加它那份 2 的幂，让整段进位归零只花 1 次，代价是段顶多出一个 1、撑死再花 1 次。长度为 1 直接减最划算；到 2 及以上进位稳赚，5 个连续 1 逐减 5 次，进位加收尾只 2 次。

于是从低位往高位扫：遇 1 先攒着，cnt 记这段连续 1 攒了多长；遇 0 按段长结算。这是贪心（每步选当下更省的处理法），扫一遍出答案。

结算一段 1 时，cnt 为什么有时归 0 有时归 1

参考代码里 n & 1 取出最低位看是不是 1，n >>= 1 把 n 右挪一位、扔掉刚看过的那位。最低位是 1 就 cnt 加一；是 0 且 cnt 大于 0，一段连续 1 到头，ans 加 1 结算。

结算后 cnt 设成几有讲究：孤立的 1（cnt 为 1）直接减掉，cnt 归 0；连续 1（cnt 大于等于 2）走进位，顶出的新 1 落在这个 0 上、成为下段起点，cnt 归 1。

100111 扫六位，39 的 3 步从哪来

39 = 100111，cnt、ans 开局都是 0。第 0 位 1，cnt=1；第 1 位 1，cnt=2；第 2 位 1，cnt=3；第 3 位 0，段长 3 进位，ans=1、cnt 归 1，对应加 1 到 40；第 4 位 0，段长 1 直接减，ans=2、cnt 归 0，对应减 8 到 32；第 5 位 1，cnt=1。

六位扫完，手上还剩 cnt=1：最高段没有更高的 0 触发结算，循环外补 1 次，ans=3，减 32 清零，正是题面写的 3。54 = 110110 同一套：低处 11 进位记 1 次，顶上来的 1 和高处两个 1 汇成段长 3，扫完补 2 次，一共 3 次。

39 扫完就返回 ans，结果为什么只有 2

时间 O(log n)（大 O 是数据每多一位、操作量跟着长多少的记法），只扫 n 的二进制位，n 不超过 10 的 5 次方也就十七位；空间 O(1)，只有 cnt 和 ans 两个变量。

循环外那两行补结算最容易被删：扫完直接返回，39 输出 2、54 输出 1；cnt 剩 1 补 1 次、剩 2 个以上补 2 次。cnt 为 2 的段同样走进位、归 1；写成 3 个以上才进位，54 就答成 4。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def minOperations(self, n: int) -> int:
        ans = cnt = 0
        while n:
            if n & 1:
                cnt += 1
            elif cnt:
                ans += 1
                cnt = 0 if cnt == 1 else 1
            n >>= 1
        if cnt == 1:
            ans += 1
        elif cnt > 1:
            ans += 2
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minOperations(int n) {
        int ans = 0, cnt = 0;
        for (; n > 0; n >>= 1) {
            if ((n & 1) == 1) {
                ++cnt;
            } else if (cnt > 0) {
                ++ans;
                cnt = cnt == 1 ? 0 : 1;
            }
        }
        ans += cnt == 1 ? 1 : 0;
        ans += cnt > 1 ? 2 : 0;
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int minOperations(int n) {
        int ans = 0, cnt = 0;
        for (; n > 0; n >>= 1) {
            if ((n & 1) == 1) {
                ++cnt;
            } else if (cnt > 0) {
                ++ans;
                cnt = cnt == 1 ? 0 : 1;
            }
        }
        ans += cnt == 1 ? 1 : 0;
        ans += cnt > 1 ? 2 : 0;
        return ans;
    }
}