Adder Without Arithmetic

MediumBit Manipulation

Problem

You are emulating a tiny processor whose ALU has no adder: it only offers AND, OR, XOR, NOT and shifts on 32-bit two's-complement registers.

Return left + right without using the + or - operators (or any library function that adds). Inputs and the result fit in a signed 32-bit integer.

Example 1

Input:
left = 1, right = 2
Output:
3

Example 2

Input:
left = -5, right = 3
Output:
-2

Example 3

Input:
left = -1, right = 1
Output:
0

The carry ripples through all 32 bits and falls off the top.

Constraints

  • -10^9 ≤ left, right ≤ 10^9
  • -2^31 ≤ left + right < 2^31

Hint

Show the first hint

Think about adding two bits: what is the sum bit, and what is the carry bit?

Walkthrough

How to approach it

01Clarify before coding

  • Are negative inputs allowed? Yes, in 32-bit two's complement.
  • Can the result overflow 32 bits? No, it is guaranteed to fit.
  • Can I use - to negate? No, only bitwise operators.

02Brute force

Increment or decrement one operand one unit at a time with a bitwise increment routine.

Cost: O(|right|) iterations, up to 10^9: far too slow.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.