[CSP-J 2020] 优秀的拆分

知识点

二进制、二进制位运算

解题思路

所有可选数均为偶数，因此奇数无解。偶数的二进制最低位为0，其余每个为1的位对应一个可选二次幂；从高位到低位输出这些幂。

正确性说明

二进制表示存在且唯一。偶数的非零位均不在第0位，得到的幂互不相同且和恰为n；奇数不可能由偶数求和得到。

易错点

2的0次幂不属于正整数次幂；输出顺序从大到小；不要把重复的2当作合法拆分。

复杂度

时间O(log n)，额外空间O(1)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;if(n&1){cout<<-1<<'\n';return 0;}
 bool first=true;for(int b=23;b>=1;--b)if(n&(1<<b)){if(!first)cout<<' ';cout<<(1<<b);first=false;}cout<<'\n';}