371. Sum of Two Integers

At a Glance

Topic: bit-manipulation
Pattern: Bitwise full adder (Bit Manipulation)
Difficulty: Medium
Companies: Facebook, Amazon, Google, Bloomberg, Microsoft
Frequency: Medium
LeetCode: 371

Problem (one-liner)

Return first + second without using + or - operators (interpret as language restriction on those tokens).

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

Forbidden arithmetic plus — use XOR for sum bits, AND for carry
Ripple carry until no carry left

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Optimal — simulate full adder: sum = first ^ second, carry = (first & second) << 1, iterate — O(32) bit width.

Optimal Solution

Go

package main

func getSum(first int, second int) int {
	for second != 0 {
		carry := (first & second) << 1
		// XOR holds sum without carry at each bit
		first = first ^ second
		second = carry
	}
	return first
}

JavaScript

function getSum(first, second) {
	let augend = first;
	let carryBits = second;
	while (carryBits !== 0) {
		const carry = (augend & carryBits) << 1;
		augend = augend ^ carryBits;
		carryBits = carry;
	}
	return augend;
}