One's Complement Arithmetic

Every programmer today learns two's complement arithmetic—the nearly universal method for representing signed integers in modern computers. But hiding in the foundations of the Internet is an older, largely forgotten number system: one's complement.

While two's complement dominates hardware design, one's complement lives on in the Internet checksum, silently verifying billions of packets every second. Its selection wasn't arbitrary; one's complement has unique mathematical properties that make it ideal for this application.

To truly master the Internet checksum and understand why it works so elegantly, we must journey back to first principles: How do we represent negative numbers in binary? What distinguishes one's complement from two's complement? And why does the difference matter for error detection?

Before diving into one's complement, let's establish the foundation: how do we represent integers in binary?

Unsigned Integers:

For n bits, unsigned integers range from 0 to 2^n - 1. Each bit position i contributes 2^i to the value when set:

Value = b_(n-1) × 2^(n-1) + b_(n-2) × 2^(n-2) + ... + b_1 × 2^1 + b_0 × 2^0

For example, in 8 bits:

• 00000000 = 0
• 00000001 = 1
• 11111111 = 255

The Challenge of Negative Numbers:

Binary naturally represents only non-negative integers. To represent negative numbers, we need a convention—a way to interpret bit patterns that might otherwise represent positive numbers as negatives. Several schemes exist:

Why Two's Complement Won:

Two's complement became the standard for processor arithmetic because:

1. Single zero: Only one representation of zero simplifies comparisons
2. Simple addition: No special cases; just add and ignore overflow
3. Hardware efficiency: The same adder circuit works for both signed and unsigned numbers
4. Symmetric operations: Negation is straightforward (invert and add 1)

Why One's Complement Survives:

Despite two's complement dominance, one's complement persists in the Internet checksum because:

1. Byte-order independence: The same algorithm works on big-endian and little-endian machines
2. Simple complementation: Negation is just bitwise NOT (no add-1 step)
3. End-around carry properties: Enable algebraic identities useful for checksums
4. Historical compatibility: Defined when one's complement machines were common

The Core Idea:

In one's complement, negative numbers are formed by inverting all bits of the corresponding positive number. This is equivalent to subtracting the number from 2^n - 1 (all-ones).

Formal Definition:

For an n-bit one's complement integer x:

• If the MSB (most significant bit) is 0: x is positive, interpreted as unsigned
• If the MSB is 1: x is negative, value is -(all-ones XOR x) = -~x in modern notation

Alternatively:

For positive x:  representation = x
For negative x:  representation = (2^n - 1) + x = (2^n - 1) - |x|

The Mystery of Negative Zero:

Notice that both 0000 and 1111 represent zero. This is negative zero—mathematically equal to positive zero but with a distinct bit pattern.

In pure mathematics, -0 = +0 always. But in one's complement:

• 0000 is the result of computing 0
• 1111 is the result of negating 0 (inverting all bits)

Both compare equal in arithmetic, but the distinct representations have interesting implications:

1. Checksum verification: When summing data with its checksum, a correct result is all-ones (negative zero), not all-zeros. This provides the elegant verification property.

2. End-around carry: Adding 1111 + 0001 produces 10000 (carry out) → 0001 after end-around carry, correctly yielding +1.

3. Historical hardware: Some machines trapped on negative zero; others normalized it. The Internet checksum embraces both representations.

Addition in one's complement differs from two's complement in one crucial way: end-around carry. When the sum produces a carry-out bit, that bit must be added back to the result.

The End-Around Carry Rule:

1. Perform standard binary addition
2. If there is a carry-out from the MSB, add 1 to the result
3. Repeat step 2 until no carry remains

This procedure is equivalent to computing the sum modulo (2^n - 1) rather than modulo 2^n.

Mathematical Justification:

Consider n-bit arithmetic. The largest representable value is 2^n - 1 (all ones). If a sum exceeds this, the carry-out represents a multiple of 2^n.

In modular arithmetic:

2^n ≡ 1 (mod 2^n - 1)

Therefore, the carry-out bit (representing 2^n) contributes 1 when reduced modulo (2^n - 1). This is precisely what end-around carry accomplishes.

Subtraction in One's Complement:

To subtract, we add the one's complement of the subtrahend:

a - b = a + (~b)

No add-1 step is needed (unlike two's complement where a - b = a + (~b + 1)).

Multiplication and Division:

These are more complex in one's complement and aren't used in checksum computation. For networks, we only need addition and complementation.

The Internet checksum leverages several algebraic properties of one's complement arithmetic. Understanding these explains why the algorithm works and enables optimizations.

Property 1: Commutativity and Associativity

One's complement addition is both commutative and associative:

a ⊕ b = b ⊕ a                    (commutativity)
(a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)        (associativity)

where ⊕ denotes one's complement addition.

Implication: The order of summation doesn't matter. We can compute partial sums in any order, parallelize computation, or use different loop orderings—all produce the same result.

Property 2: Byte-Order Independence (Detailed)

This property is subtle but crucial. Let's prove it:

Consider a block of data {b0, b1, b2, b3} (4 bytes). In big-endian, we form words:

• Word 0: (b0 << 8) | b1
• Word 1: (b2 << 8) | b3

In little-endian:

• Word 0: b0 | (b1 << 8)
• Word 1: b2 | (b3 << 8)

Let's denote:

• H = sum of all even-indexed bytes (b0, b2) in the high-byte position
• L = sum of all odd-indexed bytes (b1, b3) in the low-byte position

Big-endian sum: S_BE = (H << 8) + L + carries Little-endian sum: S_LE = H + (L << 8) + carries

S_LE is the byte-swap of S_BE!

When we complement and store the checksum in network byte order, the receiver (regardless of its native byte order) computes correctly because the swapping is consistent.

The most elegant aspect of the Internet checksum is its verification procedure. Rather than extracting the checksum, computing over remaining data, and comparing, we simply sum everything and check for a specific value.

Why Verification Works:

Let D represent the data (as a sequence of 16-bit words) and C represent the checksum.

At the sender:

C = ~(sum of all words in D)

The complement (~) means C is the additive inverse of the sum in one's complement:

sum(D) ⊕ C = sum(D) ⊕ ~sum(D) = 0xFFFF

At the receiver, we sum all words including C:

sum(D) ⊕ C = 0xFFFF

If any word is corrupted, the sum changes, and the result is no longer 0xFFFF.

Alternative Verification Result:

Some implementations check for 0x0000 instead of 0xFFFF. Both are valid:

1. If you sum all words (including checksum) and get 0xFFFF → valid
2. If you complement the sum and get 0x0000 → also valid

These are equivalent because ~0xFFFF = 0x0000.

Why 0xFFFF and Not 0x0000?

In one's complement, both 0x0000 and 0xFFFF represent zero. The convention of checking for 0xFFFF (before complement) or 0x0000 (after complement) ensures consistency across implementations.

RFC 1071 recommends checking the final sum before complement; if all bits are 1, the data is valid.

Programmers often ask: why not use simpler two's complement arithmetic for checksums? A detailed comparison illuminates the design decision.

The Byte-Order Problem with Two's Complement:

Suppose we used modulo-2^16 addition (two's complement overflow semantics). Consider data [0x01, 0x02, 0x03, 0x04]:

Big-endian:

• Words: 0x0102, 0x0304
• Sum: 0x0102 + 0x0304 = 0x0406
• Checksum: -(0x0406) mod 2^16 = 0xFBFA

Little-endian:

• Words: 0x0201, 0x0403
• Sum: 0x0201 + 0x0403 = 0x0604
• Checksum: -(0x0604) mod 2^16 = 0xF9FC

These checksums are different! A packet sent from a big-endian machine to a little-endian machine would fail verification unless explicit byte-swapping were inserted.

With one's complement and end-around carry, the checksums are byte-swapped versions of each other. When stored in network byte order, verification works on both.

Since all modern CPUs use two's complement arithmetic, implementing one's complement operations requires care. Here are the standard techniques:

Technique 1: Wider Accumulator with Deferred Folding

Use a 32-bit (or 64-bit) accumulator for 16-bit sums. After summing, fold the upper bits into the lower bits:

sum = sum_32bit
sum = (sum >> 16) + (sum & 0xFFFF)  # Fold once
sum = (sum >> 16) + (sum & 0xFFFF)  # Fold again if needed

Two folds are sufficient because the first fold can produce at most 17 bits.

Technique 2: ADC Instruction (Assembly)

The x86 ADC (Add with Carry) instruction adds the carry flag from a previous addition. This directly implements end-around carry:

xor eax, eax        ; Clear accumulator
add ax, [data]      ; Add first word
adc ax, [data+2]    ; Add second word + carry
adc ax, [data+4]    ; Add third word + carry
; ... continue ...
adc ax, 0           ; Add final carry
not ax              ; Complement

This is the fastest software implementation, achieving near-hardware speed.

Technique 3: SIMD Parallel Addition

Modern implementations use SIMD (SSE, AVX, NEON) to add multiple words in parallel, then combine results:

1. Load 8 or 16 words into SIMD registers
2. Perform parallel 16-bit adds (with no overflow loss—use wider elements)
3. Combine lane results
4. Fold to 16 bits at the end