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).

Recognition Cues

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

Diagram

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

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;
}

Walkthrough

first=15, second=32 — carries propagate in rounds until carryBits zero.

Invariant: each round applies XOR on current augend with incoming carries; next carries from AND-shift capture overlaps.

Edge Cases

• Negative numbers — two's complement; loop terminates for 32-bit width
• Zero operands

Pitfalls

• Language-specific shift / overflow on intermediate carries
• Thinking one XOR suffices — need carry ripple

Similar Problems

• 136. Single Number — XOR as invertible combine.
• 191. Number of 1 Bits — AND used differently for clear-low-bit.

Variants

• Multiply without * using add/shift.
• Add modulo power of two with masking.

Mind-Map Tags

#full-adder #xor #carry #ripple #bit-manipulation