Table of contents
Open Table of contents
Problem
Given two integers a
and b
, return the sum of the two integers without using the operators +
and 
.
Example 1:
Input: a = 1, b = 2
Output: 3
Example 2:
Input: a = 2, b = 3
Output: 5
Constraints:
1000 <= a, b <= 1000
Explanation/Approach
To solve this problem without using +
and 
operators, we utilize bit manipulation. The key idea is to simulate the addition process using bitwise operations:

Bitwise XOR (
^
) Operation: This operation is used to add two numbers without carrying. For example, in binary1 ^ 1 = 0
and1 ^ 0 = 1
. It effectively adds the bits where only one of the bits is 1. 
Bitwise AND (
&
) Operation: This operation is used to find the carry. For example,1 & 1 = 1
(carry is 1). The carry needs to be leftshifted by one, as in binary addition, a carry moves one position to the left. 
Loop until Carry is Zero: Repeat the process until there is no carry.
Solution: Bit Manipulation
class Solution:
def getSum(self, a: int, b: int) > int:
# 32bit mask in hexadecimal
mask = 0xFFFFFFFF
# Iterate till there is no carry
while b != 0:
# `a` is the partially added value, `b` is the carry leftshifted by 1
a, b = (a ^ b) & mask, ((a & b) << 1) & mask
# For negative numbers, convert `a` to a negative number
return a if a <= 0x7FFFFFFF else ~(a ^ mask)
Time and Memory Complexity
The time complexity is O(1), as the number of iterations is constant due to the fixedsize integer in Python (32 bits for this problem). The space complexity is O(1) since no additional space is used.
Explanation
The solution repeatedly applies bitwise XOR to sum bits and bitwise AND followed by left shift to calculate the carry, until there is no carry left. The mask 0xFFFFFFFF
is used to keep the integers within 32 bits (as Python integers can have more than 32 bits). For negative numbers, the complement of the result is taken to convert the result back to a negative number.
Visual Representation
Consider the example with a = 2
and b = 3
:
Initial values: a = 0010, b = 0011
Iteration 1:
Sum without carry: a ^ b = 0001
Carry: (a & b) << 1 = 0100
a = 0001, b = 0100
Iteration 2:
Sum without carry: a ^ b = 0101
Carry: (a & b) << 1 = 0000
a = 0101, b = 0000
No more carry, so the result is a = 5 (0101 in binary).