Question
Formatted question description: https://leetcode.ca/all/371.html
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.
Algorithm
Bit Manipulation
, when doing addition operation, after each bit is added, there may be a Carry generated, and then the next bit calculation needs to be added to the calculation together, then can the two parts be separated, let’s look at an example 759+ 674
- If you
do not consider
the carry, you can get 323 - If you
only consider
the carry, you can get 1110 - Put the above two numbers holiday
323+1110=1433
is the final result
Then further analysis, if you get the first and second cases above, looking at it in binary,
- Do not consider the addition of carry, 0+0=0, 0+1=1, 1+0=1, 1+1=0, this is the operation rule of
XOR
, - If you only consider the addition of carry 0+0=0, 0+1=0, 1+0=0, 1+1=1, this is actually the operation of
and
, - In the third step, when the two are added, the algorithm is called recursively, and the termination condition is that when the carry is 0, the result of the first step is directly returned.
Code
Java
-
public class Sum_of_Two_Integers { public static void main(String[] args) { Sum_of_Two_Integers out = new Sum_of_Two_Integers(); // System.out.println(out.getSum(1, 2)); // no carry // 2+2 // recurion-1: sum=0, carry= (10)左移1位 =(100)=4 // recursion-2: a=0,b=4 // recursion-3: b=0 System.out.println(out.getSum(2, 2)); // with carry } public int getSum(int a, int b) { if(b == 0){ // complete the operation when there is no carry return a; } int sum, carry; sum = a^b; // step-1 sum carry = (a&b)<<1; // step-2 sum return getSum(sum, carry);// } }
-
// OJ: https://leetcode.com/problems/sum-of-two-integers/ // Time: O(1) // Space: O(1) class Solution { public: int getSum(int a, int b) { int carry = 0, ans = 0; for (int i = 0; i < 32; ++i) { int x = (a >> i & 1), y = (b >> i & 1); if (carry) { if (x == y) { ans |= 1 << i; if (!x & !y) carry = 0; } } else { if (x != y) ans |= 1 << i; if (x & y) carry = 1; } } return ans; } };
-
class Solution(object): def getSum(self, num1, num2): """ :type a: int :type b: int :rtype: int """ ans = 0 mask = 0x01 carry = 0 for i in range(0, 32): a = num1 & mask b = num2 & mask c = carry carry = 0 if a ^ b != 0: if c == 1: carry = 1 else: ans |= mask else: if a & mask > 0: carry = 1 if c == 1: ans |= mask mask = mask << 1 if ans > 0x7fffffff: return ans - 0xffffffff - 1 return ans