当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.371.Sum of Two Integers

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^b,由于只有1+1时才有进位,所以可以通过先做按位与(&)运算再左移(<<)1位来得到进位,最后将无进位的和与进位相加就是结果

总结:

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

不用递归的话,代码为:

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代码


上一篇 LeetCode.141.Linked List Cycle

下一篇 LeetCode.007.Reverse Integer

阅读
316
阅读预计1分钟
创建日期 2018-01-29
修改日期 2018-01-30
类别
百度推荐