Skip to content

Volume ITechnology

4.30.6 — Sum of Two Integers ​

LeetCode 371 · Medium · ★ Blind 75

The problem ​

Return a + b without using + or −. Both may be negative.

Restating the Problem: You need to add two integers together, but you are forbidden from using the built-in addition or subtraction operators. This forces you to simulate how a computer's CPU Arithmetic Logic Unit (ALU) performs addition at the bit level.

  • Constraints to note: The inputs are 32-bit integers, which can be negative.
  • Edge cases: Adding a positive and a negative number, or two negatives. Handling overflow correctly in languages without bounded integers (like Python).
a = 1, b = 2     →  3
a = 2, b = 3     →  5
a = -1, b = 1    →  0

The brute force, and where it wastes work ​

The brute force here isn't about time complexity, it's about cheating the rules. One naive cheat is sum([a, b]) or utilizing built-in increment functions in a loop. The intended "brute force" bitwise simulation without handling negative numbers properly in Python will result in an infinite loop (Time Limit Exceeded). The core algorithm must precisely handle carries bit by bit.

The pattern ​

Addition is two separate operations that a CPU does in parallel, and separating them is the whole solution.

Add each column, ignoring carries. That is exactly XOR: 0+0=0, 0+1=1, 1+0=1, and 1+1=0 with the 1 carried out.

Work out the carries. A carry is generated wherever both bits are 1, which is a & b, and it belongs one column to the left, so shift it: (a & b) << 1.

Now add the sum-without-carry to the carry — which is the same problem again, so repeat until there is nothing left to carry.

python
while b:
    carry = (a & b) << 1
    a = a ^ b            # sum without carries
    b = carry            # what still needs adding
return a

This is a ripple-carry adder, and it is literally how the circuit in Chapter 1.2 works. Each iteration is one propagation step through the hardware.

Why it terminates ​

Each iteration shifts the carry one place left, so after at most 32 iterations the carry has fallen off the end and b is 0.

The Python problem ​

In most languages the loop above is the whole answer. In Python it does not terminate for negative inputs, and understanding why is the real content of this problem.

Python integers are unbounded, and a negative number behaves as though it has infinitely many leading 1s. So (a & b) << 1 keeps producing a non-zero carry forever — the 1s never run out.

The fix is to simulate 32-bit arithmetic by hand:

  1. Mask after every step with 0xFFFFFFFF, which keeps only the low 32 bits.
  2. At the end, convert back to a signed value. If the result's top bit is set, it represents a negative number in two's complement, and Python must be told: ~(result ^ 0xFFFFFFFF).

That conversion line deserves unpacking. result ^ 0xFFFFFFFF flips all 32 bits, and ~ of that gives Python's own negative representation of the same value. It is the standard idiom for "reinterpret these 32 bits as signed".

The solution ​

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

        while b:  # (3)
            carry = ((a & b) << 1) & MASK      # (4) mask to stay in 32 bits
            a = (a ^ b) & MASK  # (5)
            b = carry  # (6)

        # reinterpret the 32 bits as a signed integer
        return a if a <= MAX_INT else ~(a ^ MASK)  # (7)
ts
function getSum(a: number, b: number): number {
  while (b !== 0) {  // (3)
    const carry = (a & b) << 1;  // (4)
    a = a ^ b;  // (5)
    b = carry;  // (6)
  }
  return a;  // (7)
}

Line by line ​

Adding two binary numbers by hand works like adding decimals at school: add each column, and carry into the next column. Bit operations can do both parts for all 32 columns at once.

(1) MASK is 32 ones in binary. AND-ing with it keeps only the lowest 32 bits. Python numbers have no fixed size, so without this mask a negative number would carry forever and the loop would never end.

(2) MAX_INT is the largest positive 32-bit number, 2^{31} - 1. Any 32-bit pattern above it stands for a negative number.

(3) Keep going while there is still a carry to add.

(4) Work out every carry at once. A column carries exactly when both bits are 1, which is what a & b finds. The carry belongs one column to the left, so shift it left by one.

(5) Add every column without carrying. XOR gives 1 when exactly one of the two bits is 1. That is the sum of each column, ignoring carries: 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0 with a carry.

(6) The carries still need adding, so they become the new b, and the loop adds them in the next round. Each round, the carries move at least one column left, so after at most 32 rounds none are left.

(7) Turn the 32-bit pattern back into a Python number. If the top bit is off, the number is positive and can be returned as it is. If it is on, the pattern stands for a negative number in two's complement, the usual way computers store negative whole numbers. ~(a ^ MASK) converts it into Python's negative number with the same value.

TypeScript needs no masking, because its bitwise operators already coerce to 32-bit signed integers — the overflow behaviour you want happens for free. Java, C and C++ are the same.

Python is the awkward one precisely because its integers are better. Unbounded arithmetic is normally a gift; here it is the obstacle.

Trace ​

a = 3 (011), b = 5 (101).

iterationa ^ b(a & b) << 1new anew b
1110 (6)001 << 1 = 010 (2)62
2100 (4)010 << 1 = 100 (4)44
3000 (0)100 << 1 = 1000 (8)08
41000 (8)080

3 + 5 = 8 ✓. Four iterations, because the carry rippled through three positions.

Subtraction ​

a − b is a + (−b), and negation in two's complement is ~b + 1 — which itself needs the adder. So subtraction is one extra call:

python
def subtract(a, b):
    return getSum(a, getSum(~b, 1))

That is exactly how a CPU's ALU implements subtraction: negate and add, reusing the same adder circuit rather than building a second one.

Edge cases ​

  • One number is zero. b = 0 ends the loop at once, or a ^ 0 returns b after one round.
  • A positive and a negative number, like −1 + 1. In Python, the mask keeps the carry from running forever, and the result is 0.
  • Two negatives. The 32-bit pattern has the top bit set, and line (7) turns it back into a negative Python number.

Complexity ​

O(1) — at most 32 iterations. O(1) space.

  • Time Complexity: O(1). The while loop executes at most 32 times because we are working within a 32-bit constraint. Each shift moves the carry left until it eventually falls off.
  • Space Complexity: O(1). We only use a few integer variables (carry, a, b).

Where this goes next ​

  • Add Binary, Add Two Numbers — the same carry logic, digit by digit rather than bit by bit. 4.9.6.
  • Multiply without * — repeated shift-and-add, which is 4.28.6 Pow's structure applied to multiplication.
  • Divide Two Integers (LeetCode 29) — repeated shift-and-subtract, with a famous overflow case at INT_MIN / −1.
  • Chapter 1.2 builds the half adder and full adder as circuits, and this problem is that circuit written as software. Mentioning that connection is the strongest finish available here.

What the interviewer will push on ​

"Why is XOR the sum?" It is addition per column with the carry discarded.

"Why (a & b) << 1?" A carry is generated where both bits are 1, and it applies to the next column left.

"Why does the loop terminate?" The carry shifts left each time and falls off after 32 steps.

"Why does this break in Python?" Unbounded integers mean a negative value has infinitely many leading 1s, so the carry never dies. Mask to 32 bits and convert back to signed.

"How would you subtract?" Negate with ~b + 1 and add — which is what an ALU does.

One thing to volunteer: name it as a ripple-carry adder and say it is the circuit from Chapter 1.2. It reframes the problem from a puzzle about forbidden operators into an explanation of how the hardware actually adds.

Next: 4.30.7 Reverse Integer — the last problem in Part 4, and it is entirely about checking for overflow before it happens.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet