一个整数的2的幂次分解问题

1. 问题描述

有这样一个数列
$$
1\ 2\ 4 … 2^n… 其中n \ge 0
$$
其中每个数字仅有两个，给定一个正整数N，找到所有的可能解使得这些数字之和等于N。

2. 解法

这个数列的每个元素恰好对应于2进制数的每一位所代表的大小，而这里每个数有两个，那么每一位上可以取{0，1，2}。

Example

例如数字6的二进制数为 0110(4+2)，那么按照上面的条件同样可以写为 0102（4+2x1）、 0022(2x2+2x1)。一共三种写法。

解法一

通过递归的方法计算所有的可能数，从最高为开始扫描。因为每一位可以取0，1，2，那么可以判断最高位这些值是否合法，如果合法且有剩余，那么剩余的值又可以往后面放，当剩余值为0的时候组合计数加一。从而形成递归的方式。程序代码略。

解法二

每个二进制数的每一位最多为1，那么如果我们将一个数分解为两个数之和，然后再通过计算这两个数的占用情况，就可以得到可以每位可以为2的情况。

例如6可以分解为

$$6+0 = 0110+0000=0110\\
5+1 = 0101+0001 = 0102\\
4+2 = 0100+0010 = 0110\\
3+3 = 0011+0011 = 0022
$$
这里仅需进行到 $\lceil n/2\rceil$
因为往下计算是对称的，所以可以直接跳过。当然计算出来的结果可能有重复，然后把重复的值去除就行了。不难得出这个算法的时间复杂度为0(n).

c++代码如下：

#include <iostream>
#include <string>
#include <bitset>
#include <unordered_set>
/* 问题描述
	有这样的一个数列 1 2 4 ...2^n... n>=0
	每个数字都有2个，给定一个数number
	问有多少种组合使得这些数相加为number
*/
//这里假定数字占4个字节
size_t solution(unsigned int n) {
	std::string res(32, '0');
    //通过unordered_set去除重复元素
	std::unordered_set<std::string> s;
	for (int i = 0; i <= n / 2; i++) {
		std::bitset<32> v1(i);
		std::bitset<32> v2(n-i);
        //获得结果字符串
		for (int i = 0; i < 32; i++) {
			res[i] = v1[i] + v2[i] + '0';
		}
		s.emplace(res);
	}
	return s.size();
}

解法三

解法二的思想是通过排列的方式进行的，下面是一些观察。

对于二进制数1000 如果第一位数字1后面有零，代表没有数，那么第一位的1可以通过后一位的占用2来代替即0200。同理如果第三位的2后面有零，那么2其中的一个1也可以向上面一样通过前一位占用2来代替，即0120。以此类推还可以写为0112。一共四种，我们可以得到如下规律对于这样的数1{0}*，一共有0的个数+1种可能。
那么自然而然的想到通过每次截断1来计算可能数，如10001000通过划分1来得到可能数 1000/1000，“/” 前共有4种可能，后面有4种可能，那么一共有4x4的可能数。
细心发现，上面的分析不是完全的可能数。因为“/”后面的1000变为0200的时候对于“/”前面来说又多了一位0，当然这里只会多一位0，可以看上面1的分析，所以“/”前面的仅能多往后移一位。
1. 通过1和2的分析可以的出解法二的计算过程，当“/”前面的数占据后面多出来的0的时候，出现下列情况

xxx为“/”后的数字首位为0的情况。

首位为0的情况如何计算呢?可以通过当前

综合分析，总共的组合数应该是1的结果加上3的结果。

可以通过计算“/”前面为0的情况与斜杠后的情况的排列，加上前面占据“/”后一位0的情况。

c++代码如下

size_t solution2(unsigned int n) {
	//方法通过记记录两个数并利用排列的方法计算 
	//本例的数字都是32位所以复杂度为O（32）
	//一般情况下 O（log n）n的二进制数长度
	
	//首先把末尾的1给移走 因为最后一位为1不影响
	while (n & 1) n >>= 1;

	auto num = std::bitset<32>(n);

	size_t count_zero = 0; //记录从最低位开始扫描到1时所遍历到的0的个数
	size_t front_zero = 0;//记录分割前一次的首位为0的数量，方便下次计算
	size_t pre_res = 1; //分割前一次组合的结果

	//从最低到高扫描
	for (size_t i = 0; i < 32; i++)
	{
		//当前位为0的时候
		if (num[i] == 0) { count_zero++; }
		//当前位为1的时候 
		else {
            /*
            auto front_zero_temp = front_zero;
            //结果为 1 和 3 的分析结果
            pre_res = (count_zero+1)*pre_res+front_zero_temp;
            //计算当前首位为0的情况，方便下次使用
            front_zero = count_zero*pre_res+front_zero_temp
            由于这样会引入新的局部变量，简化为下面的式子
            */
            
			//计算首位为0的情况，方便下一次的计算
			front_zero = (count_zero)*pre_res + front_zero;
			//本次切割总共的写法
			pre_res = front_zero+pre_res;
			//归零计数
			count_zero = 0;
		}
	}
	return pre_res;
}

不难分析出时间复杂度O(logn)

总结

解法二是一个很优美的解，简单优雅，通过这种分解的方法还可以不仅课计算个数为2的解还可以解其他个数的解。只需要将分解的因子变为相应的个数。

解法三是通过一些分析和总结规律得出的，时间复杂度比较低，但是不怎么好扩展成其他的解。

（完）

2018.10.19

created by ehds

Contents

1. 问题描述

2. 解法

解法一

解法二

解法三

总结