You are given two integers a and b.
Return their sum, a + b, without using the operators + and -.
Example 1:
Input: a = 1, b = 2 Output: 3 Explanation: In binary, 01 + 10: no column has a 1 in both numbers, so nothing is carried, and the sum is 11, which is 3.
Example 2:
Input: a = 2, b = 3 Output: 5 Explanation: In binary, 010 + 011: the middle column has a 1 in both numbers, so it leaves a 0 and carries a 1 to the left. The sum is 101, which is 5.
Example 3:
Input: a = -5, b = 3 Output: -2 Explanation: Negative numbers are stored in two's complement, and the same column-by-column addition gives the right answer for them too.
Constraints:
-1000 <= a, b <= 1000
Use bitwise operations instead of + and -. Your algorithm should run in O(1) time and use O(1) extra space: it may loop once for each bit of the integer type, but no more.
Add the two numbers in binary, one column at a time, as you would on paper. In a column, 0 + 0 = 0, 0 + 1 = 1, and 1 + 1 = 10: a 0 in that column and a 1 carried into the next one. The digit left in each column is the XOR of the two bits, and a carry appears only where both bits are 1: the AND of the two bits.
a XOR b is the sum without the carries, and (a AND b) shifted left by one place is the carries. Those two numbers still add up to a + b, so repeat with them: XOR them, compute their carries, and stop when there is no carry left.
Each round moves the carries at least one place to the left, so the loop runs at most once per bit of the integer: 32 times for a 32-bit integer. That doesn't depend on the input: O(1) time.
We keep a few numbers, so the extra space is O(1).
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
