LeetCode.371.Sum of Two Integers
题目描述
- 371 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.
解题过程
不用+-符号计算整数加法。
想着应该是用位运算来做,但还是不会。一点儿思路都没有,最后上网搜了一下,可涨知识了。
思路如下:
从二进制的角度考虑,在不考虑进位的情况下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-java / problems / _371_SumOfTwoIntegers /
https://github.com/masikkk/leetcode-java/tree/master/problems/_371_SumOfTwoIntegers
上一篇 LeetCode.141.Linked List Cycle
下一篇 LeetCode.007.Reverse Integer