Two's Complement Overflow: Negative Numbers and the Bugs They Hide

The most famous bug in binary search lived undetected in Java's standard library for nine years. Joshua Bloch wrote about it in 2006. The fix is one line. The cause is two's complement overflow.

Nine years. In every JVM. On every server. Inside your Android phone.

If you write (low + high) / 2 in an interview, you are carrying that bug with you. Understanding why requires understanding how negative numbers actually live in memory, and what happens when the math overflows the container.

Why a Sign Bit Alone Doesn't Work

The naive idea: reserve the leftmost bit for the sign. 0 means positive, 1 means negative. So 0101 is 5 and 1101 is -5. Simple, right?

This creates two problems. First, you get two representations of zero: 0000 (positive zero) and 1000 (negative zero). Wasteful, confusing, and the kind of thing that causes religious arguments at CPU design meetings. Second, addition breaks. Try adding 5 and -5 with sign-magnitude:

  0101  (+5)
+ 1101  (-5)
------
 10010  (+2??)

Wrong. You need separate hardware to detect when operands have different signs and handle the subtraction manually. Early computers did this. It was, by all accounts, miserable. They had separate adder circuits for signed and unsigned numbers, and the people who maintained them did not have fun jobs.

Two's complement fixes both problems with one design.

How Two's Complement Works

Take any positive number. To get its negative counterpart:

1. Flip every bit (bitwise NOT)
2. Add 1

That's it. Let's do 5 in 8-bit:

 5   = 00000101
~5   = 11111010   (flip all bits)
~5+1 = 11111011   (add 1)

So -5 in 8-bit two's complement is 11111011. Let's verify by adding 5 and -5:

  00000101  (+5)
+ 11111011  (-5)
----------
 100000000  (9 bits, but we only have 8)

The carry bit overflows out of the 8-bit register. What's left in the register: 00000000. Zero. The arithmetic works out automatically, with no special-casing in hardware.

The hardware addition circuit does not need to know or care whether the numbers are signed. The same bits, the same adder, the same result. This is why two's complement became universal. Your CPU is secretly doing the same unsigned arithmetic for signed and unsigned numbers alike, and it's been getting away with it for decades.

The Range Asymmetry

An 8-bit signed integer can represent values from -128 to 127. Not -127 to 127. The range is not symmetric.

Why? Zero exists. Zero takes up one slot. The positive side has to share with it.

00000000  = 0
00000001  = 1
...
01111111  = 127       (INT_MAX for 8-bit)
10000000  = -128      (INT_MIN for 8-bit)
10000001  = -127
...
11111111  = -1

The most negative number, 10000000, has no positive counterpart. What happens when you try to negate it?

10000000   (-128)
flip: 01111111
add 1: 10000000  (-128 again)

Negating INT_MIN gives you INT_MIN. In 32-bit Java: Integer.MIN_VALUE is -2147483648. Math.abs(Integer.MIN_VALUE) returns -2147483648. The method doesn't throw. It doesn't warn you. It silently returns a negative number, puts it in your variable, and goes home.

Go ahead, add a Math.abs() to a sentinel value check. Ship it. See what happens six months later when someone passes the exact wrong input.

This is documented behavior. Check the Java docs for Math.abs:

Note that if the argument is equal to the value of Integer.MIN_VALUE, the most negative representable int value, the result is that same value, which is negative.

Interviewers who ask "write a function to check if a number is a palindrome" are sometimes checking whether you know this. They're not being tricky for fun. They've seen this bite people in production.

Why Two's Complement Overflow Breaks Binary Search

Here's what Bloch found. Binary search looks something like this:

def binary_search(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low + high) // 2   # BUG
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

The bug is (low + high) // 2. If low and high are both near INT_MAX (which happens with a large array), their sum overflows a 32-bit signed integer, wraps around to a large negative number, and you get an index that's negative or nonsensical.

This exact pattern was in java.util.Arrays.binarySearch and java.util.Collections.binarySearch. Every Java programmer on Earth used it. For nine years. The binary search algorithm guide covers the fix in detail, but the root cause is always the same: two operands near the max value of the type, whose sum exceeds the representable range.

In Python this never matters. Python integers are arbitrary precision. But in Java, C++, C, and Go, it absolutely can.

The fix is low + (high - low) // 2. This computes the same midpoint arithmetically but never produces an intermediate value larger than high. In Java you can also write (low + high) >>> 1, using the unsigned right shift operator, which correctly computes the midpoint even when the sum is negative.

The mathematical identity is:

(low + high) / 2  ==  low + (high - low) / 2

Proof: expand low + (high - low) / 2 = low + high/2 - low/2 = (2·low + high - low) / 2 = (low + high) / 2. Same result, no overflow.

Modulo Behavior Across Languages

Two's complement also explains why -13 % 3 gives different results in different languages.

There are two valid definitions of integer remainder. Python uses floored division: the result always has the same sign as the divisor. Java, C, C++, Go, and JavaScript use truncated division: the result has the same sign as the dividend.

# Python
-13 % 3   # = 2   (Python: floored)
13 % -3   # = -2

# Java, C, C++, Go
-13 % 3   # = -1  (truncated)
13 % -3   # = 1

If you've ever ported a hash function from Python to Java and gotten subtly wrong results on negative inputs, you have met this bug personally. The broader rules of modular arithmetic are worth reviewing separately, but the sign behavior is the piece most candidates don't expect. The standard fix in Java is:

// Java: guaranteed non-negative
int mod = ((n % m) + m) % m;

Python doesn't need this because its % is always non-negative when m is positive.

Arithmetic vs Logical Right Shift

One more place this surfaces: bit shifting with negative numbers.

Right shift has two variants. Arithmetic right shift (>>) fills the new leftmost bit with the sign bit. Logical right shift (>>>) fills with zero.

// Java (32-bit)
int x = -8;    // 11111111 11111111 11111111 11111000
x >> 1;        // 11111111 11111111 11111111 11111100  (-4)
x >>> 1;       // 01111111 11111111 11111111 11111100  (2147483644)

Arithmetic right shift divides by 2 (rounding toward negative infinity). Logical right shift treats the bits as unsigned and produces a number you probably weren't expecting.

In C and C++, right-shifting a negative number is implementation-defined behavior. You should never rely on it. C and C++ have a charming tradition of calling behaviors like this "implementation-defined," which is the language spec's way of saying your compiler gets to surprise you at inopportune moments. In Java, >> is arithmetic and >>> is logical. Python's >> is arithmetic. Go's >> on a signed type is arithmetic.

This matters for problems that ask you to count bits or manipulate the sign of a number via shifts. The bit manipulation cheat sheet has a full reference for these operators across languages.

The Language Reference

Language	-13 % 3	Right shift of negatives	Safe midpoint
Python	2 (floored)	Arithmetic (>>)	// on big ints is fine
Java	-1 (truncated)	>> arithmetic, >>> logical	low + (high-low)/2 or >>>1
C++	-1 (truncated)	Implementation-defined for signed	low + (high-low)/2
Go	-1 (truncated)	Arithmetic for signed	low + (high-low)/2
JavaScript	-1 (truncated)	>> arithmetic, >>> logical	Always 64-bit float, less issue

Say It Out Loud

None of this is arcane. Interviewers at FAANG companies actively look for the binary search midpoint bug and the INT_MIN negation trap because they're concrete signals of whether you think about overflow. There's a full breakdown of the ways integer overflow shows up in coding interviews if you want to go deeper.

When you write a binary search, say out loud: "I'll use low + (high - low) / 2 to avoid overflow." When you write a function that calls abs, say: "Edge case: INT_MIN has no positive representation in two's complement, so abs(INT_MIN) is undefined in C++ and returns INT_MIN in Java."

Those two sentences take ten seconds. They signal that you understand the model, not just the algorithm. Your interviewer is writing down what you say. Give them something to write.

The communication dimension on a coding interview rubric is not about talking for the sake of it. It's about evidence. An interviewer can't tell whether you know about overflow unless you say something.

If you want to practice this kind of reasoning out loud in a real interview format, SpaceComplexity runs voice-based DSA mock interviews with rubric feedback across exactly these dimensions.

Key Takeaways

• The range is asymmetric: INT_MIN has no positive counterpart, and negating it wraps back to itself.
• (low + high) / 2 overflows in any fixed-width integer language; use low + (high - low) / 2.
• Math.abs(Integer.MIN_VALUE) in Java returns a negative number. No warning. Handle it explicitly.
• Python's % is always non-negative when the divisor is positive. Java, C, C++, and Go inherit the sign from the dividend.

Further Reading

• Joshua Bloch, "Extra, Extra, Read All About It: Nearly All Binary Searches and Mergesorts are Broken" (2006)
• Wikipedia: Two's complement
• Java Language Specification §15.22: Bitwise and Logical Operators
• cppreference: Arithmetic operators (right shift behavior)
• Python Docs: Numeric Types, int, float, complex