个人简介
小公司研发总监，既当司令也当兵！
文章分类
相关博文
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
分类： linux
2016-07-26 17:27:55
题目：写一个函数，求两个整数的之和，要求在函数体内不得使用＋、－、×、÷。
此题考查的是发散思维，加法不用 -*/还能用什么？似乎只剩下位运算了。那么先看看2进制的加法是怎么进行的，或许从中能够找到灵感。举个简单例子，求21 17 = ？
二进制数为： 10101 10001
第一位（从低位算起）： 1 1，结果为0， 进位为1
第二位： 0 0，结果为0， 进位为0 （先不考虑低位进位的情况）
第三位： 1 0，结果为1， 进位为0
第四位： 0 0，结果为0， 进位为0
第五位： 1 1，结果为0， 进位为1
仔细观察上面的运算结果，可以发现：每一位的加法结果（1@1=0, 0@0=0, 1@0=1, @表示某种运算符），其实是一个按位异或的结果；同理，进位则是按位与的结果。
sum(10101, 10001) = 00100
carry(10101, 10001) = 10001, 注意：当前位的进位需要在高位累加，实际上carry需要右移一位
add（10101， 10001） = sum(10101, 10001) （carry(10101, 10001) << 1）= 00100 100010 = 100110 (十进制数38)
21 17 = 38，是正确答案
基于以上分析，写出程序代码就很容易了：
int bitadd (int a, int b)
{
int sum;
int carry;
int tmp;
sum = a ^ b;
carry = (a & b) << 1;
while(carry)
{
tmp = sum ^ carry;
carry = (sum & carry) << 1;
sum = tmp;
}
}
给主人留下些什么吧！~~