这是悦乐书的第 210 次更新, 第 222 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 78 题(顺位题号是 371). 计算两个整数 a 和 b 的总和, 但不允许使用运算符 + 和 - . 例如:
输入: a = 1,b = 2
输出: 3
输入: a = -2,b = 3
输出: 1
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
借助循环来实现. 先将 a 赋值给临时变量 sum, 然后判断 b 的正负, 如果 b 大于 0,sum 就自加加, 同时 b 自减减; 反之如果 b 小于 0, 则 sum 就自减减, b 就自加加, 最后返回 sum 即可.
- public int getSum(int a, int b) {
- if (a == 0) {
- return b;
- }
- if (b == 0) {
- return a;
- }
- int sum = a;
- if (b> 0) {
- while (b> 0) {
- sum++;
- b--;
- }
- } else {
- while (b < 0) {
- sum--;
- b++;
- }
- }
- return sum;
- }
03 第二种解法
因为题目说不许用加减运算符, 所以我们需要考虑使用位运算. 在做加法运算时, 会产生进位的情况. 先来看一个 53+69 例子:
如果不考虑进位做加法, 可以得到 12.
如果考虑进位做加法, 可以得到 110.
这时我们把两数 12 和 110 加起来, 就是 53 和 69 的和, 122.
如果把这种考虑位, 不考虑位的计算方式换成二进制数, 那么:
如果不考虑进位做加法, 0+0=0,1+0=1,0+1=1,1+1=0. 这其实就是异或 (^) 运算, 对应位不同时, 取 1, 否则取 0.
如果考虑进位做加法, 0+0=0,1+0=0,0+1=0,1+1=1. 这其实就是与 (&) 运算, 相同位均为 1 才是 1.
首先, 我们可以使用 a 和 b 之间的与 (&) 运算来查找进位. 其次, 我们可以在 a 和 b 之间使用异或 (^) 运算来查找不同的位, 并将其赋值给 a, 然后, 我们将进位向左移动一个位置并将其赋值给 b, 直到没有进位或 b 为 0. 最后返回 a 即可.
- public int getSum2(int a, int b) {
- if (a == 0) {
- return b;
- }
- if (b == 0) {
- return a;
- }
- while (b != 0) {
- int carry = a&b;
- a = a^b;
- b = carry << 1;
- }
- return a;
- }
04 第三种解法
我们可以将第二种解法变成递归的写法.
- public int getSum3(int a, int b) {
- if (b == 0) {
- return a;
- }
- return getSum3(a ^ b, (a&b) << 1);
- }
05 小结
算法专题目前已连续日更超过两个月, 算法题文章 78 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/9ca62dd71dd9