LeetCode笔记:371. Sum of Two Integers
问题:
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -. Example: Given a = 1 and b = 2, return 3.
大意:
计算a和b两个整数的和,但是不能用+或-运算符。 比如: 给出 a = 1 和 b = 2,返回 3.
思路:
这道题乍看之下很简单,计算两个数之和嘛,但问题在于不能直接使用加号和减号,这就尴尬了,不过如果不这样,也称不上一道题了。其实对于运算,我们知道计算机本身就是没有什么加减乘除的,一切都是二进制在进行一些位运算,所以这里很显然的一个思路也就是转换成位运算,当然如果你本来就知道加法的实现原理,那也可以直接拿来做了。
我们先看个位数的二进制运算: 1 + 1 = 10; 1 + 0 = 1; 0 + 1 = 1; 0 + 0 = 0。
如果我们用^,也就是位异或运算来做: 1 ^ 1 = 0; 1 ^ 0 = 1; 0 ^ 1 = 1; 0 ^ 0 = 0。
其实观察可以看到,异或和直接的加唯一结果有区别的就是1+1这一条,但是换个想法,1+1是要进位的,进位后个位上还是变成0了,这样就一样了,只不过还需要有一个进位操作,而对于二进制,只有都是1的时候才会进位,这立马就可以联想到“与”操作了对不对: 1 & 1 = 1; 1 & 0 = 0; 0 & 1 = 0; 0 & 0 = 0。
既然是进位,我们当然要将得出来的结果进一位,这里使用左移运算符就可以了,所以对于1+1这种的做法就是异或加上与的进位: 1+1 = 1^1 + (1&1)<<1
当然我们还是不能有加号,所以对上那个加法我们还是要使用同样的方法,这就是递归了,那要到什么时候为止呢,从逻辑上来说,到不再有进位就可以了。
现在我们看一个二位数的加法:11+ 10 = 101
首先11^10 = 01, 然后11&10 = 10,左移一位得100, 现在有进位,那么继续 01+100, 01^100 = 101, 01&100 = 000, 这时候与操作后的结果为0了,可以停止运算了,最后的的结果应该是101,答案正确。说明思路是对的。
代码(Java)
public class Solution {
public int getSum(int a, int b) {
if (b == 0) return a;
int sum,up;
sum = a^b;
up = (a&b)<<1;
return getSum(sum, up);
}
}
代码很简单,递归调用,在每次调用中都先检查进位的计算是不是为0了,也就是是不是没有进位了,如果没有了说明异或运算就是最终结果了,如果还有进位就继续算下去,算异或和与之后的左移然后继续调用。
看来这些看似理所当然的最简单的运算符,内里的门道也是需要了解清楚的。
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十