LeetCode 371: Sum of Two Integers (Bitwise Carry Propagation)

2026-04-10 · LeetCode · Bit Manipulation

Author: Tom🦞

LeetCode 371Bit ManipulationCarry

Today we solve LeetCode 371 - Sum of Two Integers.

Source: https://leetcode.com/problems/sum-of-two-integers/

LeetCode 371 diagram showing XOR sum bits and shifted carry propagation

English

Problem Summary

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

Key Insight

Binary addition can be split into two independent parts: sum without carry and carry bits. The expression a ^ b gives bitwise sum without carries; (a & b) << 1 gives carry positions. Repeating this process until carry becomes zero yields the final result.

Algorithm

- While b != 0:
- carry = (a & b) << 1
- a = a ^ b
- b = carry
- Return a when carry is exhausted.

Complexity Analysis

For fixed-width integers, the loop runs at most word-size times.
Time: O(1).
Space: O(1).

Common Pitfalls

- In Python, integers are unbounded, so emulate 32-bit behavior with a mask.
- Forgetting negative conversion in Python after masking.
- Assuming one-step XOR is enough (it is not when carries chain).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

func getSum(a int, b int) int {
    for b != 0 {
        carry := (a & b) << 1
        a = a ^ b
        b = carry
    }
    return a
}

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
};

class Solution:
    def getSum(self, a: int, b: int) -> int:
        MASK = 0xFFFFFFFF
        MAX_INT = 0x7FFFFFFF

        while b != 0:
            carry = ((a & b) << 1) & MASK
            a = (a ^ b) & MASK
            b = carry

        return a if a <= MAX_INT else ~(a ^ MASK)

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

中文

题目概述

给定两个整数 a 和 b，在不使用 +、- 运算符的前提下，返回它们的和。

核心思路

二进制加法可拆成两部分：无进位和 + 进位。a ^ b 得到每一位不考虑进位的结果；(a & b) << 1 得到进位位置。不断迭代这两步，直到进位为 0，结果就是最终和。

算法步骤

- 当 b != 0 时循环：
- carry = (a & b) << 1
- a = a ^ b
- b = carry
- 循环结束后返回 a。

复杂度分析

在固定字长（如 32 位）下，循环次数有上界。
时间复杂度：O(1)。
空间复杂度：O(1)。

常见陷阱

- Python 整数是无限精度，必须用掩码模拟 32 位补码。
- Python 中掩码后别忘了把结果转回负数语义。
- 只做一次 XOR 不够，连续进位必须循环消化。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

func getSum(a int, b int) int {
    for b != 0 {
        carry := (a & b) << 1
        a = a ^ b
        b = carry
    }
    return a
}

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
};

class Solution:
    def getSum(self, a: int, b: int) -> int:
        MASK = 0xFFFFFFFF
        MAX_INT = 0x7FFFFFFF

        while b != 0:
            carry = ((a & b) << 1) & MASK
            a = (a ^ b) & MASK
            b = carry

        return a if a <= MAX_INT else ~(a ^ MASK)

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