P7071 [CSP-J 2020] 优秀的拆分

解题思路

显然 $2$ 的正整数次幂都是偶数，多个偶数相加不可能得到奇数。因此 $n$ 为奇数时无解，输出 -1。

若 $n$ 为偶数，则它的二进制最低位为 $0$，而二进制第 $i$ 位（$i>0$）刚好对应 $2$ 的 $i$ 次幂。

因此用 1<<31-__builtin_clz(n) 取出当前 $n$ 的二进制最高位对应值，从大到小依次输出并减去即可。

参考代码

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	if(n&1)
	{
		cout<<-1<<'\n';
		return 0;
	}
	while(n)
	{
		int t=1<<31-__builtin_clz(n);
		cout<<t<<' ';
		n-=t;
	}
	return 0;
}