CSP-J 2020优秀拆分：二进制拆分与位运算实战解析

1. 先把题目翻译成人话

1.1 题目要求到底说了什么

P7071 [CSP-J 2020] 优秀的拆分 是入门组第一题，放在整套试卷的开头位置，按理说是用来稳定军心的“签到题”。但我发现，每年都有不少同学在这道题上翻车，最大的原因不是不懂二进制，而是没有把题目的限制条件读清楚。

题目说的是：给你一个正整数 n，需要把 n 拆成若干个不同的“2 的正整数次幂”之和。如果存在这样的拆分，就按从大到小的顺序输出每一个 2 的幂；如果不存在，就输出 -1。

注意几个关键词：正整数次幂、若干个、不同。这里“正整数次幂”强调的是 2¹、2²、2³ 这样的数，也就是 2、4、8、16……而 2⁰=1 不在允许范围内。这一点特别关键，因为很多新手把 2⁰ 也算进去，导致对无解的判断出现偏差。

举个例子。n=6，可以拆成 4+2，也就是 2²+2¹，这样每个幂都不同，而且都是正整数次幂，所以 6 是一个有优秀拆分的数，输出“4 2”。而 n=7 呢？7 的二进制是 111，也就是 4+2+1，但 1 这个项是 2⁰，不符合“正整数次幂”，所以 7 没有优秀拆分，输出 -1。

这道题适合谁来读？如果你是刚开始学信息学竞赛的新手，这篇文章能帮你把二进制表示、位运算和简单特判串起来；如果你已经会做了，也可以看一下我在文末整理的边界条件和常见坑，回头集训时少踩雷。

1.2 先用小数据建立直觉

我们在脑子里把几个数过一遍：

观察这张表能得出一个非常强的结论：一个数能不能做优秀拆分，好像只跟它的奇偶性有关。奇数全都不行，偶数全都可以。这不是巧合，背后的道理就在下一节。

2. 从二进制理解拆分的本质

2.1 每个正整数只有一种二进制写法

先退一步想一个基础问题：为什么“若干个不同的 2 的幂相加”这个话题绕不开二进制？

因为二进制本身就是一种用“不同的 2 的幂”表示整数的方式。一个二进制数从低位到高位，每一位的位权分别是 2⁰、2¹、2²、2³……如果某一位是 1，就代表这一位对应的 2 的幂被选中了；如果某一位是 0，就代表没选中。所以任意正整数 n，它的二进制表示中所有为 1 的位对应的幂加起来，恰好等于 n，而且因为二进制表示唯一，这种“选哪些位”的方式也是唯一的。

比如 13，二进制是 1101，也就是 8+4+1，即 2³+2²+2⁰。又比如 20，二进制是 10100，也就是 16+4，即 2⁴+2²。

所以，题目里说的“若干个不同的 2 的正整数次幂之和”，本质上就是问你：n 的二进制表示里，所有为 1 的位对应的 2 的幂，是不是都满足“正整数次幂”这个条件。满足，就按位输出；不满足，就输出 -1。

这段话看起来简单，但它其实一次性回答了两个问题：一是“存在性”，二是“怎么输出”。输出方案根本不用搜索，也不用回溯，直接看二进制位就行。

2.2 奇数为什么会无解

现在来解释那张表里的现象。

如果一项是 2 的正整数次幂，那么这一项必定是 2 的倍数，也就是偶数。若干个偶数相加，结果一定是偶数。所以，一个奇数如果要做优秀拆分，它必须至少包含一个奇数项，但题目又不允许 2⁰=1 这种唯一的奇数次幂出现，于是奇数天然没有合法拆分。

反过来，任何一个偶数 n，它的二进制表示最低位一定是 0。也就是说，它的二进制表示里根本不存在 2⁰ 这一位。既然没有 2⁰，那么剩下的所有为 1 的位，对应的幂至少是 2¹，全都是正整数次幂。把这些幂全部输出，就是一个合法的优秀拆分。

这里有一个初学者容易绕进去的细节：偶数 2 本身，二进制是 10，只有一位 2¹，当然可以；偶数 4，二进制是 100，只有一项 4；偶数 6，二进制是 110，有两项 4 和 2；偶数 8，二进制是 1000，只有一项 8。你看，偶数拆出来不会出现“空拆”的情况，因为 n 至少是 2。实际上 n 的最小偶数是 2，而 2 本身就是一项合法幂。

所以这道题的存在性判断只需要一句话：n 是奇数，输出 -1；n 是偶数，一定有解。 不需要枚举，不需要递归，更不需要贪心去拼凑组合。

2.3 代码里为什么先判奇偶

位运算里判断奇偶，最标准的写法是 if (n & 1)。它的原理是：一个二进制数的最低位如果是 1，说明这个数是奇数；如果最低位是 0，说明是偶数。n & 1 只保留最低位，结果不是 0 就是 1，所以能直接当布尔值用。

明白这个原理之后，整个程序的主框架就固定了：

1. 读入 n。
2. 如果 n & 1 为真，直接输出 -1 并结束。
3. 否则，遍历 n 的二进制位，把所有为 1 的位对应的 2 的幂输出。

第三步有个细节必须想清楚：既然是偶数，最低位一定是 0，所以遍历时理论上可以不用管第 0 位。但为了代码语义更明确，有的选手会直接从高到低遍历到 1，而不是遍历到 0。这不会影响结果，因为偶数第 0 位本来就是 0。

3. 两种常用写法，照着写就能过

3.1 按位从高往低扫描

这是最直观的写法：枚举每一个二进制位，看这一位是否为 1。注意 P7071 要求按从大到小输出，所以我们要从高位往低位枚举。

cpp复制#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    if (n & 1) {
        cout << -1 << '\n';
        return 0;
    }

    for (int i = 30; i >= 1; --i) {
        if ((n >> i) & 1) {
            cout << (1 << i) << ' ';
        }
    }
    cout << '\n';
    return 0;
}

这里有几个点值得你细看。

第一，(n >> i) & 1 是把 n 右移 i 位，然后取最低位。如果结果是 1，就说明第 i 位原本是 1，对应的幂是 2 的 i 次方，也就是 1 << i。

第二，循环为什么从 30 开始而不是从 31 开始？因为 1 << 31 在 32 位有符号 int 里会溢出，变成负数，这个行为很危险。对于这道题的数据范围，用 int 读入 n 绰绰有余，从 i=30 开始已经完全覆盖了常见题目的规模。如果实在不放心，也可以把左移写成 1LL << i，用 long long 避免数组越界式的溢出。

第三，循环终点是 i=1，不是 i=0。原因就是题目不允许 2⁰。当然，因为 n 是偶数，i=0 的时候 (n >> 0) & 1 本来就是 0，写 i=0 也不会输出错东西，但写 i=1 能让语义更贴合题目：我们只允许正整数次幂。

这个写法的时间复杂度是 O(log n)，空间复杂度 O(1)。

3.2 lowbit 逐位摘除法

第二种写法很多选手也喜欢用，它就是“每次取最低位的 1，然后减掉，直到 n 变成 0”。

cpp复制#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    if (n & 1) {
        cout << -1 << '\n';
        return 0;
    }

    vector<int> ans;
    while (n > 0) {
        int low = n & (-n);
        ans.push_back(low);
        n -= low;
    }

    reverse(ans.begin(), ans.end());

    for (int x : ans) {
        cout << x << ' ';
    }
    cout << '\n';
    return 0;
}

lowbit 是树状数组里经常出现的小工具，n & (-n) 能保留 n 的二进制里最低位的 1。比如 n=20，二进制是 10100，最低位的 1 对应的值是 4，所以 n & (-n) 等于 4。

这个写法会从低到高把 2 的幂一个个摘出来，但题目要求从大到小输出，所以最后必须 reverse 一下。你可以用 vector 存，也可以用一个 stack，或者先递归再输出。反正核心思想就是：把一个偶数拆成若干二进制位，再把它们反向排列。

很多同学觉得 lowbit 写法难懂，其实它非常适合用来验证自己对位运算的理解。你可以在纸上模拟一遍 n=20：第一次取到 4，n 变 16；第二次取到 16，n 变 0；存下来是 [4, 16]，reverse 后是 [16, 4]，输出“16 4”，正好是 20 的优秀拆分。

3.3 两种写法怎么选

我个人的建议是：初学者优先掌握按位扫描法。它的逻辑更接近题目要求，“从高到低看每一位”，天然满足输出顺序，也不容易出现遗漏。lowbit 写法的代码更短，但需要额外反转，新手在赛场上容易忘记这一步而写错顺序。

不管你选哪种，最后提交前都要对几个边界数据做测试，别以为自己写完就万事大吉。

4. 我踩过的坑和易错点

4.1 最常见的错：漏掉奇数特判

这道题如果只做“输出二进制位”这一步，不管奇偶，那奇数也会被拼出一个包含 1 的拆分。比如 n=3，二进制是 11，如果直接扫描，会输出“2 1”，但题目要求这样的 n 输出 -1。这个 1 就是不合法的 2⁰。

我见过不少同学在本地测了 6、10、12 这些偶数样例，全都通过，结果一提交就 WA。原因就是没有拿 1、3、7 这种奇数去测。所以做这道题的第一条铁律就是：奇数必须特判为 -1，并且要放在所有逻辑的最前面。

其实这个坑的本质不是不会写，而是不习惯“存在性判断”类的题目。竞赛题有时候不是让你构造答案，而是先问你“存不存在”。这种题必须先把无解的情况想清楚，再想怎么构造解。

4.2 输出顺序搞反

P7071 的题意是按从大到小输出。比如 n=6 要输出“4 2”，不是“2 4”。很多平台在判题时对顺序非常严格，你输出反了，即使拆分的项完全正确，也会被判错。

为什么会反？因为按位扫描法如果从低位往高位扫，或者 lowbit 法最后没有 reverse，都会输出反序。我之前带集训队时，专门让队员们互相测过这种样例，一开始大概有四分之一的人会栽在顺序上。

解决这个问题最稳的方法，不是靠记“要反过来”，而是靠样例。你只要死死盯住一个样例 n=6，记住标准答案是“4 2”，然后跑一下自己的程序，如果输出的是“2 4”，马上就知道哪里需要调整。

4.3 移位操作里的溢出隐患

1 << i 这个表达式本身很漂亮，但如果你让 i 达到 31，在 32 位 int 下就是未定义行为，严格来说是 UB。在竞赛环境下，它可能会输出一个负数，也可能因为编译器优化产生非常奇怪的结果。

选手们常用的规避手段有两类。一类是限制 i 的范围，比如这道题从 30 往下扫，就不会碰到 1 << 31。另一类是全部用 long long 来写：

cpp复制for (int i = 60; i >= 1; --i) {
    if ((n >> i) & 1) {
        cout << (1LL << i) << ' ';
    }
}

这样写的好处是，即使 n 的数据范围更大，代码也能应对。但要注意，n 本身也得用 long long 读入，否则 n 在移位前就被截断了。

我见过一个比较可惜的失误：选手把 n 定义成 int，但是循环里用 1LL << i，结果当 i=31 时，n >> i 已经把 n 当成有符号数移位了，依然可能出问题。所以类型要统一。如果本题你确定 n 的范围在 int 内，就用 int 从 30 往下扫；如果不确定，就用 long long 从 60 往下扫，两条路都通。

4.4 建议的自测数据清单

每次写完这种题，不要急着交，先在本地把这组数据过一遍：

这组数据覆盖了“最小奇数”“单个幂”“偶数多幂”“最大单幂”“连续多幂”等典型情况。你只要把这组测过，基本不会在基础扣分点上翻车。

5. 这题背后的思维扩展

5.1 本质是“二进制拆分”

把这道题看透之后你会发现，它正式的名字其实是“二进制拆分”。所谓优秀拆分，就是把一个正整数的二进制表示里所有为 1 的位对应的幂列举出来。限制条件“2 的正整数次幂”不过是不让你把 2⁰ 算进去。

二进制拆分是一个很底层、很常用的思想。它在信息学竞赛里无处不在：快速幂、状态压缩、多重背包的二进制优化、树状数组、倍增算法……全都和它有关。

单看这道题，它就是让你对每个二进制位进行一次判断。复杂度是 O(log n)，n 再大也不怕，因为一个数的二进制位数增长非常慢。2 的 30 次方已经超过 10 亿，所以 int 范围内最多扫 30 位；2 的 60 次方已经超过 10 的 18 次方，long long 范围内最多扫 60 位。

这个特性让二进制拆分类算法在竞赛里有一种天然优势：它能处理数据范围很大的题目，因为 log n 级别的扫描几乎可以忽略不计。

5.2 从输出答案到分组工具的迁移

二进制拆分的威力不止于“把一个数拆开”。它还能用来表达“任意不超过某个上限的数量”。

举一个最常见的例子：多重背包问题中，如果某一种物品有 m 件，直接一件一件拆着做会超时，更聪明的做法是把它按二进制分组拆成 1、2、4、8、16……件。这样做的理由是：从这组数中选取若干个，可以凑出 0 到 m 之间的任意一个整数。换句话说，我们不再需要枚举每一件物品，只需要枚举 log m 个组。

这和“优秀的拆分”中的原理完全一样：一个二进制位集合能表示的唯一数值，就是这个集合对应的二进制数；而不同的二进制位组合，能覆盖连续的一段整数范围。

很多同学在做难题时卡住，不是因为那个问题的逻辑有多玄，而是因为缺少这种基础模型的迁移能力。如果你能把一道签到题的理解延伸到背包优化，那么这道题对你来说就有了远超本身的收获。

5.3 如果题目稍微变形，你还能马上反应吗

我把几个常见的变形拿来说说，你在脑子里过一遍答案。

如果题目允许 2⁰，也就是允许用 1，那么所有正整数就都有解了，奇数也能拆。此时按位扫描的循环应该从高到低扫到 0，并且 n=7 应该输出“4 2 1”。

如果题目要求从小到大输出，那代码就更加简单了：用 lowbit 直接从低到高输出，完全不需要 reverse。

如果题目要求输出的是“拆成了多少项”，那就是求 n 的二进制里有多少个 1。偶数时直接统计，奇数时无解。C++ 里可以用 __builtin_popcount(n) 一步到位。

如果题目要求判断“是否存在某个幂至少出现两次”，那就是另一类重复拆分的模型，不是做位运算，而是做贪心或找规律。

这一串变形说明，P7071 的核心知识点不是“背一个输出模板”，而是真正理解二进制位和 2 的幂之间的关系。理解了这种关系，改不动题目风格，也能活得很好。

6. 复盘与个人心得

从第一次见到这道题，到后来用类似的框架去做多重背包优化，我最大的体会是：简单题别急着写完就跑，多花三分钟想清楚“为什么能这样做”，比多刷三套卷子都有用。

这道题最值得记住的两个结论是：一是奇数无解，因为不能使用 2⁰；二是偶数的解，就是它二进制表示中所有 1 位对应的幂。第一个结论用来判无解，第二个结论用来构造答案。这两句话一握牢，整道题的代码其实就是几行位运算。

最后还是想提醒一下做比赛的读者：样例过了不代表一定对，尤其像这种带 -1 输出、带顺序要求的题，必须自己准备几组刁钻数据。奇数、大偶数、恰好是 2 的幂的数，这三个类别一定要测。我自己在训练时吃过不少“样例都对，交上去 WA”的亏，后来养成了写完题先列边界数据的习惯，正确率明显提升。

如果你刚学到这里，接下来可以试试不看代码，自己在编译器里从零把它写一遍。能一次性写出“判断奇偶 + 高位扫描 + 正确换行”并跑过全部自测数据，说明这一关就真正过了。