算法题每日一练---第63天：优秀的拆分

一、问题描述

一般来说，一个正整数可以拆分成若干个正整数的和。

假如一个正整数可以拆分成若干个不同的 2 的正整数次幂相加的形式，那么称它为优秀的拆分。

例如，10=8+2=2^3+2^1是一个优秀的拆分。但是，7=4+2+1=2^2+2^1+2^0 就不是一个优秀的拆分，因为 1 不是 2 的正整数次幂。

现在，给定正整数 n，你需要判断这个数的所有拆分中，是否存在优秀的拆分。若存在，请你给出具体的拆分方案。

题目链接：优秀的拆分

二、题目要求

样例 1

输入： 10
输出： 8 2

样例 2

输入： 7
输出：-1

考察

位运算
建议用时15~30min

三、问题分析

本题是位运算的第18题，没了解过位运算相关知识点可以看这一篇文章，讲解比较详细：

算法题每日一练---第45天：位运算

简单来说，这一题需要判断一个数字能否拆成不同2的次幂相加组成，202^020不算在内。

如果输入的是奇数，输出-1，不存在。

int 32位可以存储这一题的数据量，举一个例子：

10->2进制:  1 0 1 0
对应10进制：8 0 2 0

那么我们只需要对数字的二进制从2进制的头（即31位）开始右移与计算，如果为1，输出对应的10进制结果，为0就跳过。

四、编码实现

#include<iostream>#include<math.h>usingnamespacestd;
intmain()
{   
longlongi,j,n,k;//初始化数据cin>>n;//输入nif(n%2!=0)//奇数直接输出-1    {
cout<<-1;
return0;
    }
else    {
for(i=31;i>=0;i--)//从2进制31位开始右移计算        {
if(n&(1<<i))//如果的当前位是1            {
k=pow(2,i);
cout<<k<<" ";//输出结果            }
        }
    }
return0;
}

五、测试结果