当前位置:首页 » 面试笔试 » 正文

不用加减乘除做加法

11591 人参与  2019年03月20日 19:09  分类 : 面试笔试  评论

题目描述

写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。

这道题看起来非常有趣,既然做加法,但却不让使用+、-、*、/四则运算符号,很多同学看了一眼就懵逼了,这可难倒八戒了。

我们来分析一下,如果不让用四则运算符合,那显然就是用递归了。为啥呢?原因很简单,递归程序里可以不需要运算符合,只要有递归结束条件即可。

举个例子,比如2+3=?

2用二进制表示是0010

3用二进制表示是0011

不用四则运算,我们就该想到使用逻辑运算符,与、或、非、异或,同或等。

显然,我们需要用到与、异或

异或相当于不带进位的加法:

1^0=1,

0^1=1,

0^0=0,

1^1=0

也就是:

image.png

与运算符正好我们可以用来求进位:

1&0=0,

0&1=0,

0&0=0,

1&1=1  (此时进位)

image.png

num4是两数做与操作后得到的结果左移一位。为啥需要左移一位呢,哈哈,原因很简单,进位嘛,向高位进位,当然要左移啦!

如上面两图所示,num3代表不进位的加法得到的结果,num4是进位得到的值。二者相加,就是最终结果,而题目要求不能使用加法,因此,我们就继续递归啊!(原因是咱们的递归程序就是在做加法操作)

那么最重要的问题来了,递归程序的结束条件是什么呢?

当进位为0时,直接返回num3就可以了!代码如下:


int Add(int num1, int num2) 
{     
        if(num2 == 0) 
        { // 进位为0时,返回
            return num1;
        }
        int num3 = num1 ^ num2; // 不考虑进位
        int num4 = (num1 & num2) << 1; // 进位
        return Add(num3, num4); 
}



来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=1237

程序员面试  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!