Abstract / Summary

Add two integers without using the plus operator by using bitwise operations.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 56% (1+ million submissions).

Typical patterns to solve this problem:

• Bit Manipulation
• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements two public methods: increment and getSum. increment adds one to a 16-bit signed integer using only bitwise operations, deliberately allowing overflow to wrap around. getSum computes the sum of two 32-bit integers without using the + operator for the main addition; it relies on increment to perform the necessary unit increments. The method first orders the inputs, reduces the problem to a combination of a left shift and a series of increments, and finally returns the computed result.

Key Steps

Increment Function

short increment(short x)
{
    // find bit=0, clear all bits along the way
    int mask = 1;
    // overflow is okay and intended
    while (x & mask)
    {
        x ^= mask;
        mask <<= 1;
    }

    return x | mask;
}

The function starts with a mask set to the least-significant bit. It iterates while the current bit of x is set, clearing that bit with XOR and moving the mask left. When a zero bit is encountered, the loop exits and the mask is OR-ed into x, effectively turning that zero into one while leaving higher bits unchanged. Because the mask is an int, the shift can propagate beyond the 16-bit range, allowing the function to wrap from 0x7FFF to -0x8000 (two’s-complement overflow) without special handling.

GetSum Function

int getSum(int a, int b)
{
    if (a > b)
        swap(a, b);

    // short => 16 bits
    short aa = a;
    short bb = b;
    // a+b = 2*a + (b - a)
    int result = aa << 1;

    // slowly increment aa by 1 until bb - aa == 0
    while (aa < bb)
    {
        aa     = increment(aa);
        result = increment(result);
    }

    return result;
}

The method begins by ensuring a is not larger than b; if it is, the two values are swapped. Both operands are then cast to short, truncating them to 16 bits. The expression aa << 1 computes 2 * a using a left shift, which is a fast arithmetic operation.

The core loop increments aa one step at a time until it reaches bb. For each increment of aa, the result variable is also incremented, thereby accumulating the difference b - a onto the initial 2 * a. When the loop terminates, result holds the value a + b as intended.

Edge Cases Handled

When a and b are equal, the while (aa < bb) condition is false from the start, so the loop body is skipped and the function returns 2 * a, which matches a + b.

If either a or b exceeds the range of a 16-bit signed integer, the cast to short truncates the value modulo 2¹⁶. The subsequent arithmetic proceeds on these truncated values, and the overflow behavior of increment ensures that the wrap-around continues correctly.

The increment routine explicitly tolerates overflow: when x is 0x7FFF (the maximum positive short), the loop clears all bits and the final OR sets the sign bit, yielding -0x8000. This behavior aligns with two’s-complement arithmetic and prevents undefined behavior on overflow.

The initial swap guarantees that the loop condition aa < bb is well-defined even when the original inputs are supplied in reverse order, eliminating the need for a separate branch to handle a decreasing sequence.

Performance Optimizations

The left shift aa << 1 replaces a multiplication by two with a single CPU instruction, reducing the computational cost of the initial term.

The increment function avoids a full addition operation; instead, it flips trailing ones to zero and sets the first zero to one. This bit-twiddling approach typically requires fewer cycles than a generic addition, especially when the number of trailing ones is small.

By using a short for the loop variables, the algorithm limits the number of iterations to at most 2¹⁶ steps, which is a bounded range independent of the original 32-bit input size. This bounded loop size can be advantageous for predictable execution time on platforms where the cost of each iteration is modest.

The combined use of swap, casting, and the incremental loop ensures that the heavy lifting is performed with simple, low-level operations that map efficiently to processor instructions, minimizing the overhead associated with higher-level arithmetic functions.

Imagine that computers speak in a secret language made only of zeros and ones. Every number is just a long line of these little switches that are either off or on. When a person wants to add two numbers together, the computer takes those lines of switches and performs a dance to combine them into a new number.

The code here is like a little robot helper designed to add two numbers, but it likes to do things in a very specific way. Instead of just adding the numbers all at once like we do with arithmetic, it breaks the task into tiny steps.

It starts by taking one of the numbers and making it twice as big, which is a shortcut the computer can do very quickly. Then, it enters a loop. Think of a loop like a playground merry-go-round that spins over and over again. Inside this merry-go-round, the robot has two jobs. It adds one tiny bit to the first number, and because it changed the first number, it also has to add one tiny bit to the total result to keep everything fair.

The robot keeps spinning around this playground, adding one bit at a time, until the first number has grown until it catches up to the second number. Once they have caught up to each other, the robot stops spinning. The total result it has been building inside the merry-go-round is the final answer, which is the sum of the two starting numbers. It is a slow and steady way to reach the finish line, but it makes sure that every single switch is in the right place at the end.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java		Python					TS
	WalkCCC	C++	Java		Python
	leetcode.ca	C++	Java		Python				Go
	LeetcodeHelp	C++	Java		Python
	Progiez	C++	Java		Python
github	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai		Java
	Dijkstra-Edu		Java
	everthis					JS
	fartem							Ruby
	FelixFan1122			C#
	fsq	C++
	halfrost								Go
	haoel	C++
	JoshCrozier					JS
	linouk23	C++
	lkwq007				Python
	qiyuangong				Python
	ruoru						Rust
	sonugiri1043	C++
	suxrobGM			C#
	varunu28		Java
	vthwang		Java
	wisdompeak	C++
	XiaotaoGuo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
Dijkstra-Edu	Java
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fsq	C++
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
qiyuangong	Python
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vthwang	Java
wisdompeak	C++
XiaotaoGuo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality