Chinaunix首页 | 论坛 | 博客
  • 博客访问: 671470
  • 博文数量: 141
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1114
  • 用 户 组: 普通用户
  • 注册时间: 2014-03-17 14:32
个人简介

小公司研发总监,即当司令也当兵!

文章分类

全部博文(141)

分类: 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;
}
}


阅读(2547) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~