当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.371.Sum of Two Integers 不用加减号计算整数加法

LeetCode.371.Sum of Two Integers 不用加减号计算整数加法

题目描述

371 Sum of Two Integers
https://leetcode-cn.com/problems/sum-of-two-integers/
https://leetcode.com/problems/sum-of-two-integers/description/

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.


相似题目

LeetCode.371.Sum of Two Integers 不用加减号计算整数加法
LeetCode.067.Add Binary 二进制求和

LeetCode.剑指offer.064.计算1到n的和

LeetCode.069.Sqrt(x) x的平方根
LeetCode.050.Pow(x,n) 实现Pow(x,n)


解题过程

不用+-符号计算整数加法。
想着应该是用位运算来做,但还是不会。一点儿思路都没有,最后上网搜了一下,可涨知识了。

思路如下:
从二进制的角度考虑,在不考虑进位的情况下a+b=a^b,由于只有1+1时才有进位,所以可以通过先做按位与(&)运算再左移(<<)1位来得到进位,最后将无进位的和与进位相加就是结果。

异或 ^ 被称为不进位的加号
左移 << 是一种进位或者乘法符号
公式:a + b = ( a ^ b ) + ( ( a & b ) << 1 )

对于本题
1、a + ba 的问题拆分为 (a 和 b 的无进位结果) + (a 和 b 的进位结果)
2、无进位加法使用异或运算计算得出
3、进位结果使用与运算和移位运算计算得出
4、循环此过程,直到进位为 0

不用递归的话,代码为:

class Solution {
    public int getSum(int a, int b) {
        int sum = a ^ b;//不考虑进位的和
        int carry = (a & b)<<1;//进位
        while(carry!=0){//直到进位为0,结束
            int newsum = sum ^ carry;
            carry = (sum & carry)<<1;
            sum = newsum;
        }
        return sum;
    }
}

用递归的话就更简单了,只需要一行:

class Solution {
    public int getSum(int a, int b) {
        return b==0 ? a : getSum(a^b,(a&b)<<1);
    }
}

GitHub代码

algorithms/leetcode/leetcode/_371_SumOfTwoIntegers.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_371_SumOfTwoIntegers.java


上一篇 LeetCode.141.Linked List Cycle 判断链表是否有环

下一篇 LeetCode.007.Reverse Integer

阅读
评论
479
阅读预计2分钟
创建日期 2018-01-29
修改日期 2018-01-30
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论