You get two integers, a and b.
Return a + b. Your code may not use + or -.
Example 1:
Input: a = 4, b = 9 Output: 13 Explanation: In binary, this is 0100 + 1001. No column has two 1s, so nothing carries. The sum is 1101, which is 13.
Example 2:
Input: a = 7, b = 1 Output: 8 Explanation: In binary, this is 111 + 001. The last column has two 1s. It writes 0 and carries 1. In each of the next two columns, the carry meets a 1. Each time, it writes 0 and carries 1 again. The sum is 1000, which is 8.
Example 3:
Input: a = -9, b = 4 Output: -5 Explanation: The computer stores negative numbers in two's complement. Adding column by column works for them too.
Constraints:
aandbare each from -1,000 to 1,000.
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. PRO is unlimited.
Saved
Ctrl + Enter to check
