Sum of Two Integers
Given two integers `a` and `b`, return the sum of the two integers without using the operators `+` and `-`.
Examples
Constraints
-1000 <= a, b <= 1000
Bitwise XOR and AND
Approach
We can simulate binary addition using bitwise operators. The XOR operation `a ^ b` gives the sum of `a` and `b` without the carry bits. The AND operation `(a & b) << 1` gives the carry bits. We can assign the sum without carry to `a`, and the carry bits to `b`, and repeat this process until `b` becomes 0 (no more carry). Note: In Python, integers have arbitrary precision, so we need to manually simulate 32-bit integer overflow by masking the result with `0xFFFFFFFF`. If the result is negative, we need to convert it back to a standard Python negative integer.
Complexity Analysis
Time complexity is O(1) because the loop will run at most 32 times (size of an integer in bits). Space complexity is O(1).
class Solution { public int getSum(int a, int b) { while (b != 0) { // Carry bits int carry = (a & b) << 1; // Sum without carry a = a ^ b; // Assign carry to b for the next iteration b = carry; } return a; }}