Sum of Two Integers

Medium
415.

Sum of Two Integers

MediumMathBit ManipulationAmazonMicrosoftAppleBloombergHulu

Sum of Two Integers is a medium coding problem on math and bit manipulation, asked in Amazon, Microsoft, Bloomberg and Apple interviews.

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

Example 1

Input
a = 1, b = 2
Output
3

Example 2

Input
a = 2, b = 3
Output
5

Example 3

Input
a = -1, b = 1
Output
0

Constraints

  • -1000 <= a, b <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var getSum = function(a, b) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in
AI InterviewGet started

Sum of Two Integers — Solution in Python, Java & C++

Sum of Two Integers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Sum of Two Integers is a medium coding problem on math and bit manipulation, asked in Amazon, Microsoft, Bloomberg and Apple interviews.

Problem statement

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

Example 1

Input: a = 1, b = 2
Output: 3

Example 2

Input: a = 2, b = 3
Output: 5

Example 3

Input: a = -1, b = 1
Output: 0

Constraints

  • -1000 <= a, b <= 1000

Hints for Sum of Two Integers

  1. Hint 1

    a ^ b adds the bits while ignoring every carry.

  2. Hint 2

    (a & b) << 1 is exactly the carry that was ignored.

  3. Hint 3

    Loop, feeding the carry back in, until it becomes zero — and keep the arithmetic inside 32 bits so negatives work.

How to solve Sum of Two Integers

a ^ b is the sum without carries and (a & b) << 1 is the carry; loop feeding the carry back until it is zero, masking to 32 bits.

Approach

  1. Mask both operands to 32 bits.
  2. While y != 0: carry = ((x & y) << 1) & mask, x = (x ^ y) & mask, y = carry.
  3. Reinterpret x as signed.

Why it works

Binary addition is exactly XOR plus shifted carry, and each iteration pushes the carry one bit higher, so it vanishes within 32 iterations.

Complexity

  • Time — O(32)
  • Space — O(1)

Pitfalls

  • In Python the mask is what makes negative results terminate; in a fixed-width language the shifts wrap naturally.

Reference solution

Python

def getSum(a: int, b: int) -> int:
    mask = 0xFFFFFFFF
    x, y = a & mask, b & mask
    while y:
        carry = ((x & y) << 1) & mask
        x = (x ^ y) & mask
        y = carry
    return x if x <= 0x7FFFFFFF else ~(x ^ mask)

Java

public static int getSum(int a, int b) {
    int x = a, y = b;
    while (y != 0) {
        int carry = (x & y) << 1;
        x = x ^ y;
        y = carry;
    }
    return x;
}

C++

int getSum(int a, int b) {
    unsigned int x = (unsigned int) a, y = (unsigned int) b;
    while (y != 0) {
        unsigned int carry = (x & y) << 1;
        x = x ^ y;
        y = carry;
    }
    return (int) x;
}

JavaScript

var getSum = function(a, b) {
    let x = a | 0, y = b | 0;
    while (y !== 0) {
        const carry = (x & y) << 1;
        x = (x ^ y) | 0;
        y = carry | 0;
    }
    return x | 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Bit Manipulation