一、任务
将一个给定的正整数分解成2的不同次幂的和。例如：
7 = 4 + 2 + 1
9 = 8 + 1
虽然9可以分解成4+4+1，但这种分解方法包含两个2的2次幂，不符合要求，8+1是符合要求的。
可以证明，这种分解是唯一。（不过我的数学是体育老师教的，我不会证啊。）
二、环境
Win7中文旗舰版64位 + Python 3.64 64位
Win7中文旗舰版64位 + GCC 4.5.2
三、Python代码
这里给出两种方法。
第一种方法是将n看成二进制，分别跟二进制数的各位权重进行与运算，如果结果不为0，说明n在相应的位为1，那么，相应权重对应的十进制数就是分解结果里面的一个。
第二种方法充分利用了Python的内置函数bin和enumerate构造列表生成式，一个语句搞定分解结果。
代码如下：
def f(n):
if n <= 0:
rlist = []
else:
rlist, weight = [], 1
while weight <= n:
if weight & n:
rlist.append(weight)
weight *= 2
return rlist
def f2(n):
if n <= 0:
return []
else:
return [2**pos for (pos, value) in enumerate(list(bin(n)[-1:1:-1])) if value != '0']
if __name__ == "__main__":
a = 19
print("%d=%s" % (a, "+".join(list(map(str,f(a))))))
print("%d=%s" % (a, "+".join(list(map(str,f2(a))))))
运行结果：
19=1+2+16
19=1+2+16
四、C语言代码
思想：n反复除以2，非零余数对应的二进制位的权顺次存入数组。
#include <stdio.h>
int f(int n, int x[])
{
int i = 0, weight = 1;
if (n>0)
{
while (n>0)
{
if (n % 2)
x[i++] = weight;
n = 2;
weight *= 2;
}
}
return i;
}
int main()
{
int a[64], n = 19, count, i;
if ((count = f(n, a)) <= 0)
printf("%d无法分解。", n);
else
{
printf("%d=%d", n, a[0]);
for (i = 1; i < count; i++)
printf("+%d", a[i]);
}
}
运行结果：
19=1+2+16
五、应用
1、应用一
某部队武器库保管员将1000发子弹放在十个盒子里，一旦有人来拿子弹，只需告诉他一千以内所需子弹的个数，他都可以拿出若干个盒子，凑出所需的子弹数，而不必打开盒子去数子弹。试问：
（1）十个盒子里各放多少发子弹？
（2）如果有人来领n（1<=n<=1000）发子弹，保管员会拿出哪几个子弹盒子？试编程求解该问题。
（3）对于一个正整数n（1<=n<=1000），可能对应的领子弹盒子方案不止一种。如果要求拿出来的子弹盒子数目是所有可能方案中最少的，又该怎么编写程序？
2、应用二
给定一个文件，请输出该文件具有如下四种属性中的哪几种？
四种属性是：只读、系统、隐藏、存档。
