Description
Add two integers without using addition or subtraction operators in the solution. Inputs and sum fit signed 32-bit integers.
Solution
def get_sum(a, b):
mask = 0xffffffff
a &= mask
b &= mask
while b:
a,b = (a ^ b) & mask, ((a & b) << 1) & mask
return a if a <= 0x7fffffff else ~(a ^ mask)Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[2,3]- Output
5
Carries combine with the differing bits to produce five.
Example 2
- Input
[-4,3]- Output
-1
The positive operand partially cancels the negative one.
Example 3
- Input
[-2,-3]- Output
-5
Two negative operands yield -5.
Approach
XOR gives the sum without carries; shifted AND gives carries. Repeat until no carries remain.
Time & space
O(32) = O(1) time; O(1) auxiliary space for fixed 32-bit integers.