Subtraction in binary numbers

2026-04-11

Subtraction without '-' operation to keep CPU operations simple.

Goal

The goal of this post is to explain why and how subtraction is executed without the - operation in modern computers.

Background

The CPU uses a set of logic circuits.

  • AND
  • OR
  • XOR
  • NOT
  • Shift

Early computers had very limited resources, so they had to execute many kinds of operations with only a few logic circuits.

Addition is simple

Addition is very simple. We only use AND, XOR, and shift.

Example:

5 = 0101
3 = 0011

First, we calculate the sum without carry using XOR.

0101
0011
----
0110

Second, we calculate the carry using AND.

0101
0011
----
0001

We shift the carry result to the left because that carry is added to the next bit position.

0001 << 1 = 0010

Finally, we add the XOR result and the shifted carry.

0110
0010
----
1000 = 8 = 5 + 3

So we can perform addition with XOR, AND, and shift.

Subtraction is not simple

In subtraction, we need to handle borrow. For example:

 12
- 5
----
 2 - 5, we borrow 1 from 12, so 12-5=7

Subtraction is a bit more complex than addition. Should we introduce a new CPU operation? No, we want to keep CPU logic simple. So what should we do? Can we perform subtraction with the existing operations?

Subtraction in binary

We can convert subtraction to addition:

12-5 = 12 + (-5)

So we need a way to represent negative values, and then we can reuse the addition logic.

Complement numbers

A complement is a value that is added to another value to reach a specific total (usually a power of the base). Example:

# base is 10
1000 - 345 = 655
complement of 345 = 655

With a complement, we can convert subtraction to addition:

1000 - 345
= 1000 + 655
= 1655
-> discard the leading digit, then 655

Complement numbers in binary

If we use 8-bit numbers, we can use 2^8 = 256 as the total. Example:

# -3 in 8-bit
2^8 = 256

256 - 3 = 253
in binary, 11111101 = -3

Let's verify:

  3 = 00000011
- 3 = 11111101

00000011
11111101
--------
1 00000000

discard the carry-out bit, and the 8-bit result is 00000000.

We can calculate a negative value in binary as:

-x = ~x + 1

~x flips the bits, and then we add 1.

In Python

In Python, integers are arbitrary precision, so there is no fixed bit width.

In that case, if we keep shifting carry for negative numbers, carry can continue indefinitely. For example:

-3 = ...11111111111111111101

So the binary representation is effectively unbounded in Python. To avoid this, we manually apply a fixed-width mask.

  • -1000 <= a, b <= 1000
class Solution:
    def getSum(self, a: int, b: int) -> int:
        mask = 0xFFFFFFFF  # 2^32-1, all 32 bits set to 1
        
        while b != 0:
            a, b = (a ^ b) & mask, ((a & b) << 1) & mask
        
        max_int = 0x7FFFFFFF  # 2^31-1, max 32-bit signed int
        return a if a <= max_int else ~(a ^ mask)

~(a ^ mask):

Example:

a
11111111111111111111111111111101

mask
11111111111111111111111111111111

XOR
00000000000000000000000000000010

This inversion is interpreted in the 32-bit range.

a ^ mask
= 00000000000000000000000000000010

Finally,

# ~x = -(x+1)
~00000000000000000000000000000010
= -3