不使用+加号实现正整数的求和相加

有人问了我如何在不使用加号的情况下计算两个正整数的和，这让我想起了原来学习计算机组成原理的时候所讲的内容，也就是只使用逻辑运算就可以实现加法了，这里记录一下。

原理

首先以一个10进制的加法作为例子，例如18+23，如下面的竖式：

1 8
+
2 3
——-

首先8+3=11，这里要进一位，然后1+2=3，3加上进位最终等于41。

仔细分析，如果我们不加上进位，而是把进位先忽略掉，那么结果就是8+3=11,不进位就是8+3=1，然后1+2=3，这时候结果就是31，然后把结果与之前的进位相加就变成了31+1*10=41(个位的进位在十位上，所以乘以10),最终结果依然是对的。

所以这里的原理也就是在计算的时候先不进行进位，而是先求得不进位的结果，然后再将结果与进位的值相加，就可以得到正确结果了。

计算机中，数据都是使用二进制保存的，归根到底，我们所计算的十进制加法最终都会转换成二进制的数据进行计算，而二进制是满二进一，例如我们计算二进制 1011+0010，按照上面的方法，首先忽略进位，计算的结果是1001，然后将进位加上，1001+1<<2(二进制中<<向左移位，也就是1<<2=100)结果是1101。

看到这里有人会说了，如果加上进位依然有进位怎么办？仔细想一想可以明白，每一次与进位相加依然是做了一次加法，这不就是一个递归的过程么，直到需要相加的进位为0为止。

依然以一个二进制加法为例，1011+0010，如果不计算进位的加，那么结果应该是1011+0010=1011^0010 = 1001（^是异或），而进位信息应该是(1011&0010)<<1 =0100，这下应该很清楚了吧，计算不带有进位的结果使用^，求取进位信息使用& 。

C++实现代码

递归方法:

//使用递归方法
unsigned int RecursionAdd(unsigned int a,unsigned int b){
	if(0==b){
		return a;
	}else{
		//返回非进位结果与进位值相加
		return RecursionAdd(a^b,(a&b)<<1);
	}
}

非递归方法

//使用非递归方法
//非递归的加
unsigned int NormalAdd(unsigned int a,unsigned int b){
	//用于保存非进位加的值
	unsigned int c=0;
	while(true){
		if(b==0){
			return a;
		}else{
			//保存a的值
			c = a;
			//计算非进位的结果
			a =a^b;
			//计算进位值
			b=(c&b)<<1;
		}
	}
}