Chinaunix首页 | 论坛 | 博客
  • 博客访问: 107327
  • 博文数量: 18
  • 博客积分: 226
  • 博客等级: 二等列兵
  • 技术积分: 183
  • 用 户 组: 普通用户
  • 注册时间: 2011-08-24 18:31
文章分类

全部博文(18)

文章存档

2013年(9)

2012年(7)

2011年(2)

我的朋友

分类: C/C++

2013-08-14 16:32:49

    今天在群里面看到一群友问这个问题,随之百度了一下,觉得如此高级,遂记录之。。。

点击(此处)折叠或打开

  1. int add(int a, int b)
  2. {
  3.     if(!a) return b;
  4.     else return add((a&b)<<1, a^b);
  5. }
用位操作进行加法运算,主要思想是将加法的计算结果分解为两部分:第一是不考虑进位的运算结果,第二是进位,然后再将这两者相加,即得到结果。详细表述如下:
(1)不考虑进位的计算结果,以一位二进制数来表示:
1+1=0
1+0=1
0+1=1
0+0=0
这个过程可以用异或位运算符来表示,即:
1^1=0
1^0=1
0^1=1
0^0=0
则a^b表示不考虑进位的计算结果。
(2)进位,同样以一位二进制数表示:
0+0→不进位
0+1→不进位
1+0→不进位
1+1→进位,即相当于是10,将10加到不考虑进位的计算结果上,即可得到整个的计算结果,而可以用位运算的与操作和向左的移位操作即可模拟上述的是否进位:
0&0=0       (0&0)<<1=0
0&1=0       (0&1)<<1=0
1&0=0       (1&0)<<1=0
1&1=1       (1&1)<<1=10
如此,即将运算结果计算出来了。

    接下来,需要按照递归的方式将上述思想实现,主要原因是将运算结果分为不考虑进位的运算结果A和进位值B,则计算结果为A+B,但该运算可能还是会产生进位,估将A和B再次采用这种计算方法进行计算,知道进位部分为0,即表示上次加法计算没有进位,则上次加法计算的不考虑进位的运算结果,即为整个加法计算的结果。
阅读(2099) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~