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

Windows C/C++ 浅灬笑 3839℃ 0评论

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

原理

首先以一个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;
		}
	}
}

 

转载请注明:悠然品鉴 » 不使用+加号实现正整数的求和相加

喜欢 (0)or分享 (0)
发表我的评论
取消评论

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址