How do you solve Sum of Two Integers Without Using '+' Operator?

Use a loop that continues while the carry (b) is non-zero. In each iteration, compute carry as (a & b) << 1, update a as a ^ b (sum without carry), and update b as carry. When carry becomes zero, a contains the final sum. Masking with 0xffffffff simulates 32-bit integer overflow behavior, ensuring correct results for negative numbers in Python's unlimited integer representation.

Sum of Two Integers Without Using '+' Operator

Q: What is the time complexity of Sum of Two Integers Without Using '+' Operator?

O(1). The loop runs at most 32 times for 32-bit integers, as each iteration propagates carry bits one position to the left, guaranteeing termination in constant time.

Q: What pattern does Sum of Two Integers Without Using '+' Operator use?

The Pattern: Bit Manipulation (Iterative Carry Propagation) The Heuristic: Addition without '+' can be achieved by iteratively combining sum bits (XOR) and carry bits (AND shifted left), propagating carry until none remains, effectively simulating binary addition at the bit level.

Medium Bit Manipulation

Problem

Given two integers a and b, return the sum of the two integers without using the '+' or '-' operators.

−10⁹ ≤ a, b ≤ 10⁹

Example

Input: a = 1, b = 2

Output: 3

The straightforward addition using '+' is disallowed. Instead, the algorithm uses bitwise operations to simulate addition. XOR (^) computes the sum bits without carry, while AND (&) followed by a left shift (<< 1) computes the carry bits. Iteratively applying these operations accumulates the sum until no carry remains. For example, starting with a=1 (01) and b=2 (10): - XOR: 01 ^ 10 = 11 (sum without carry) - AND and shift: (01 & 10) << 1 = 00 (carry) Since carry is zero, the sum is 3 (11 in binary).

Approach

Straightforward Solution

Using the '+' operator directly adds the two numbers in O(1) time. However, the problem forbids '+' and '-', so this approach is invalid.

Core Observation

Addition can be decomposed into two parts: sum without carry and carry bits. XOR operation yields the sum bits ignoring carry, while AND operation identifies carry bits. Shifting the carry bits left aligns them for the next addition step.

Path to Optimal

Preview

The key recognition signals are 'sum without using +' and 'bitwise operations'. These indicate Bit Manipulation because addition can be simulated by combining XOR and AND operations iteratively…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a loop that continues while the carry (b) is non-zero. In each iteration, compute carry as (a & b) << 1, update a as a ^ b (sum without carry), and update b as carry…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(1)

The loop runs at most 32 times for 32-bit integers, as each iteration propagates carry bits one position to the left, guaranteeing termination in constant time.

Space

O(1)

Only a fixed number of integer variables and bitwise operations are used, requiring constant auxiliary space.

Pattern Spotlight

Bit Manipulation (Iterative Carry Propagation)

Addition without '+' can be achieved by iteratively combining sum bits (XOR) and carry bits (AND shifted left), propagating carry until none remains, effectively simulating binary addition at the bit level.

Solution

Python

1class Solution:
  def getSum(self, a: int, b: int) -> int:
      mask = 0xffffffff
      
      while (b & mask) > 0:
          carry = (a & b) << 1
          a = a ^ b
          b = carry
          
      return (a & mask) if b > 0 else a

Step-by-Step Solution

Simulate 32-bit Integer Behavior with Masking

3	`mask = 0xffffffff`

Objective

To constrain the integers to 32-bit representation, simulating overflow and enabling correct handling of negative numbers in Python.

Key Insight

Python integers are unbounded, so bitwise operations can produce unexpected results for negative numbers. Applying a mask of 0xffffffff limits values to 32 bits, mimicking fixed-width integer behavior. This ensures that operations like carry propagation and final result extraction behave as expected for signed 32-bit integers.

Interview Quick-Check

Core Logic

Masking with 0xffffffff confines all intermediate results to 32 bits, enabling correct simulation of signed integer overflow.

Common Pitfalls & Bugs

Omitting the mask leads to infinite loops or incorrect results for negative inputs due to Python's unlimited integer size.

Iteratively Compute Sum and Carry Until No Carry Remains

To repeatedly update the sum and carry bits until the carry becomes zero, yielding the final sum.

Return Final Result with Correct Sign Handling

To return the final sum, correctly handling negative results by applying the mask conditionally.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 6 Critical

carry = (a & b) << 1

Calculate carry bits by ANDing a and b, then shifting left.

AND identifies bits where both a and b have 1s, indicating a carry is needed; shifting left aligns these carry bits with the next higher bit position for addition in the next iteration.

Line 5 Critical

while (b & mask) > 0:

Continue loop while carry bits exist within 32-bit range.

The loop condition ensures the algorithm iterates only while there are carry bits to propagate, preventing infinite loops and guaranteeing termination.

Line 7 Critical

a = a ^ b

Compute sum bits without carry using XOR.

XOR adds bits without considering carry, effectively summing bits where only one of a or b has a 1, which is the core of bitwise addition.

Full line-by-line criticality + rationale for all 6 lines available on Pro.

Test Your Understanding

Why does the algorithm use XOR for sum and AND followed by left shift for carry in each iteration?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Sum of Two Integers Without Using '+' Operator from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Sum of Two Integers Without Using '+' Operator drill

or drill a free problem

1	`class Solution:`
2	`def getSum(self, a: int, b: int) -> int:`
3	`mask = 0xffffffff`
4
5	`while (b & mask) > 0:`
6	`carry = (a & b) << 1`
7	`a = a ^ b`
8	`b = carry`
9
10	`return (a & mask) if b > 0 else a`