Hide sidebar
leetcode/DSA courseSystem Design

Sum of Two Integers

Bit Manipulation
MediumLeetCode #371
15 min

Problem Statement

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

Example

Example 1:

Input: a = 1, b = 2

Output: 3

Solution (Bitwise Addition)

This problem can be solved using bitwise operators to simulate the process of addition. The core idea is to use XOR (^) to handle the sum without considering carries, and AND (&) to find the carries.

Algorithm Steps

  • Use XOR to find the sum of two numbers without carry.
  • Use AND and a left shift to find the carry.
  • Add the carry to the sum.
  • Repeat until there are no more carries.

a

00000001

b (carry)

00000010

Start: a = 1 (00000001), b = 2 (00000010)

Sum of Two Integers Solution

class 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