算法之道----不用加，减， 乘 ，除 计算 a+b的值

       在面试笔试中会考到这类题目，要求不用加减乘除运算来计算两数和，其实考的就是位运算。

 

       规则1：

       如果1010+0101 = 1111在计算上不产生进位， 则1010^0101 = 1010+0101 = 1111   

     

      上面1010和 0101 二进制加法计算的特点是没有进位，所以他们的二进制加法和按位异或运算结果才会相同。但是如果如果是二进制加法运算有进位，则明显以上等价关系就不能成立。

 

       思路：如 20(10100)+25(11001)  =45二进制加法运算会产生进位，那我们把他转换成a和b两个数 满足a+b = 20+25 = 45且a和b二进制加法不会产生进位，按照规则1有 20+25  = a + b = a ^ b，明显我们可以找到一个例子 a=32(100000) b=13(001101)满足上述要求。

 

       如何找到a 和 b：

当产生进位的时候，我们可以试着把产生进制的位置找出来， 20(10100)+25(11001) 进行按位与运算

10100&11001 = 10000  可知道在最高位是两个1相与，故在最高位产生进位，10100^11001 = 01101这个结果是不进位的结果，只要我们把不进位的异或运算加上进位时候带来的结果增量加起来，就是我们最终想要的结果10100+11001 = 101101 .

结果为：10100^11001+（10100&11001）<<1 =  01101+10000 <<1

a  =  01101

b =  10000 <<1 = 100000--->左移位后的结果即为进位产生的增量

 

如果a   b还不满足上面思路中的要求的话，在继续重复上面的过程，知道找出满足思路中的啊a，b的值。

 

代码如下：

#include "stdio.h"
int bitAdd(int a ,int b){
	printf("第一次递归 bitAdd(%d ,%d )\n",a,b );
	int jin = a&b;//进位
	int notJin = a^b;
	if (jin!=0)
	{
		return bitAdd(jin<<1,notJin);
	}else{
		return notJin;
	}
	return 0;
}
 int main()
{
	int a ,b;
	printf("输入两个数做加法(空格隔开)\n");
	scanf("%d %d",&a,&b);
	printf("结果:%d+%d=%d",a,b,bitAdd(a,b));
	return 0;
}

 结果：

 

       

 

 

 

评论

7 楼 chenchuangfeng 2013-03-27  

lj830723 写道

问题是在实际开发中这样的使用是否直观，我不是否定使用位运算，而是在理论和实践中尽量的使用能够清晰明了的写法，这样有助于后期的维护和交接。说实话，当我看到这样的代码，第一感觉就是脑壳疼

这显然不是应用在实际开发...这个只是一道笔试题。是考察队底层运算的理解，实例开发肯定是不用这么去写

6 楼 lj830723 2013-03-27  

问题是在实际开发中这样的使用是否直观，我不是否定使用位运算，而是在理论和实践中尽量的使用能够清晰明了的写法，这样有助于后期的维护和交接。说实话，当我看到这样的代码，第一感觉就是脑壳疼

5 楼 chenchuangfeng 2013-03-27  

ansjsun 写道

chenchuangfeng 写道

mengqingyu 写道

这么写比直接运算快很多？实际测过吗？

测试没有..不过底层全是二进制表示，cpu进行加法运算也是通过这样的思路去计算的。

这么容易测试的事情..为什么不去试试呢...效率应该是一样的....说实话..这点优化纯粹就是自找麻烦

这个不是优化算法.....是一些面试笔试题。

4 楼 ansjsun 2013-03-27  

chenchuangfeng 写道

mengqingyu 写道

这么写比直接运算快很多？实际测过吗？

测试没有..不过底层全是二进制表示，cpu进行加法运算也是通过这样的思路去计算的。

这么容易测试的事情..为什么不去试试呢...效率应该是一样的....说实话..这点优化纯粹就是自找麻烦

3 楼 chenchuangfeng 2013-03-27  

mengqingyu 写道

这么写比直接运算快很多？实际测过吗？

测试没有..不过底层全是二进制表示，cpu进行加法运算也是通过这样的思路去计算的。

2 楼 mengqingyu 2013-03-27  

这么写比直接运算快很多？实际测过吗？

1 楼 justjavac 2013-03-27  

在计算机底层，所有的运输都是通过位运算进行的。这个问题只要学过底层的都轻而易举。