Sum of Two Integers (LeetCode 371)

LC 371 — Problem

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

Input: a = 1, b = 2

Output: 3

Input: a = 2, b = 3

Output: 5

Constraints: -1000 ≤ a, b ≤ 1000

You know that 5 + 3 = 8. But what if someone took away your + operator? No - either. The only tools left: &, |, ^, <<, >>. Five bitwise operations — and somehow you need to produce 8.

This is not a contrived puzzle. Every CPU on the planet adds numbers using exactly these primitives. The + operator in your code compiles down to a circuit built from AND gates, XOR gates, and shift registers. You are about to build that circuit yourself.

FIG. 1 — INPUTS IN BINARY

00000101

(5)

00000011

(3)

— every bit is a column waiting to be added —

Your toolbox: &, |, ^, <<, >>. Which of these could produce 8 from 5 and 3? Tap each operator to see what it gives you. Pay attention to the binary — the answer is hiding in the bit patterns.