Loading learning content...
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?
By the end of this page, you will understand one's complement representation completely: how numbers are encoded, how arithmetic works, the concept of negative zero, end-around carry, and why these properties made it perfect for the Internet checksum. You'll be able to perform one's complement calculations by hand and in code.
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 = 000000001 = 111111111 = 255The 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:
| Method | Representation of -1 | Range | Zero Representations |
|---|---|---|---|
| Sign-magnitude | 10000001 | -127 to +127 | Two (00000000, 10000000) |
| One's complement | 11111110 | -127 to +127 | Two (00000000, 11111111) |
| Two's complement | 11111111 | -128 to +127 | One (00000000) |
| Excess-K (K=128) | 01111111 | -128 to +127 | One (10000000) |
Why Two's Complement Won:
Two's complement became the standard for processor arithmetic because:
Why One's Complement Survives:
Despite two's complement dominance, one's complement persists in the Internet checksum because:
Early computers (UNIVAC, CDC 6600, PDP-1) used one's complement arithmetic natively. The Internet checksum was designed in the 1970s when these machines were still in use. The algorithm was deliberately chosen to work efficiently on both one's complement and two's complement hardware—a remarkable feat of portable design.
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:
Alternatively:
For positive x: representation = x
For negative x: representation = (2^n - 1) + x = (2^n - 1) - |x|
| Binary | Decimal Value | Notes |
|---|---|---|
| 0111 | +7 | Maximum positive |
| 0110 | +6 | |
| 0101 | +5 | |
| 0100 | +4 | |
| 0011 | +3 | |
| 0010 | +2 | |
| 0001 | +1 | |
| 0000 | +0 | Positive zero |
| 1111 | -0 | Negative zero (equals +0) |
| 1110 | -1 | ~0001 = 1110 |
| 1101 | -2 | ~0010 = 1101 |
| 1100 | -3 | ~0011 = 1100 |
| 1011 | -4 | |
| 1010 | -5 | |
| 1001 | -6 | |
| 1000 | -7 | Minimum negative |
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 01111 is the result of negating 0 (inverting all bits)Both compare equal in arithmetic, but the distinct representations have interesting implications:
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.
End-around carry: Adding 1111 + 0001 produces 10000 (carry out) → 0001 after end-around carry, correctly yielding +1.
Historical hardware: Some machines trapped on negative zero; others normalized it. The Internet checksum embraces both representations.
In one's complement, to negate a number, simply invert all bits. No addition of 1 is needed. This makes the final step of checksum computation (complementing the sum) extremely fast—just a bitwise NOT operation.
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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
"""One's Complement Arithmetic Examples Demonstrates addition with end-around carry.""" def ones_complement_add_16bit(a: int, b: int) -> int: """ Add two 16-bit one's complement numbers. Returns the 16-bit one's complement sum. """ # Standard addition (may produce 17+ bit result) result = a + b # End-around carry: fold all overflow bits back while result > 0xFFFF: # Add the carry bits back to the lower 16 bits result = (result & 0xFFFF) + (result >> 16) return result def ones_complement_negate(x: int, bits: int = 16) -> int: """ Negate a one's complement number (just invert all bits). """ mask = (1 << bits) - 1 return (~x) & mask # Example 1: Adding positive numbersprint("=== Example 1: 0x0003 + 0x0005 ===")result = ones_complement_add_16bit(0x0003, 0x0005)print(f"0x0003 + 0x0005 = 0x{result:04X} ({result})") # Expected: 0x0008 # Example 2: Adding with overflow (end-around carry needed)print("=== Example 2: 0xFFFE (-1) + 0x0003 (+3) ===")result = ones_complement_add_16bit(0xFFFE, 0x0003)print(f"0xFFFE + 0x0003 = 0x{result:04X}")# 0xFFFE (-1) + 0x0003 (+3) should equal +2# Standard add: 0xFFFE + 0x0003 = 0x10001 (17 bits, carry out!)# End-around: 0x0001 + 0x0001 = 0x0002 ✓ # Example 3: Adding two negative numbersprint("=== Example 3: 0xFFFC (-3) + 0xFFFB (-4) ===")result = ones_complement_add_16bit(0xFFFC, 0xFFFB)print(f"0xFFFC + 0xFFFB = 0x{result:04X}")# -3 + -4 = -7# In one's complement 16-bit: -7 is ~0x0007 = 0xFFF8# Standard add: 0xFFFC + 0xFFFB = 0x1FFF7 (carry!)# End-around: 0xFFF7 + 0x0001 = 0xFFF8 ✓ # Example 4: Adding positive and negative zeroprint("=== Example 4: 0x0000 (+0) + 0xFFFF (-0) ===")result = ones_complement_add_16bit(0x0000, 0xFFFF)print(f"0x0000 + 0xFFFF = 0x{result:04X}")# Should be zero. 0x0000 + 0xFFFF = 0xFFFF (negative zero) ✓ # Example 5: Demonstrating checksum verificationprint("=== Example 5: Checksum Verification ===")data_sum = 0x4500 + 0x0073 + 0x0000 + 0x4000 + 0x4011data_sum = ones_complement_add_16bit(data_sum, 0xC0A8) # Continues...data_sum = ones_complement_add_16bit(data_sum, 0x0001)data_sum = ones_complement_add_16bit(data_sum, 0xC0A8)data_sum = ones_complement_add_16bit(data_sum, 0x00C7)checksum = ones_complement_negate(data_sum)print(f"Sum before complement: 0x{data_sum:04X}")print(f"Checksum (~sum): 0x{checksum:04X}") # Verify: sum of data + checksum should be 0xFFFFverification = ones_complement_add_16bit(data_sum, checksum)print(f"Data sum + Checksum = 0x{verification:04X}")print(f"Valid: {verification == 0xFFFF}")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.
When implementing one's complement in two's complement languages (all modern languages), you must be careful. A single end-around carry step may not suffice if the result still overflows. Loop until no overflow remains, or use a sufficiently wide accumulator (e.g., 32 bits for 16-bit checksums).
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:
In little-endian:
Let's denote:
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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960
"""Demonstrating byte-order independence of one's complement sum. Key insight: The checksum values in different byte orders are byte-swapped versions of each other. When placed in the headerin network byte order (big-endian), verification works on any machine.""" def ones_complement_sum(data: bytes, byte_order: str) -> int: """Compute one's complement sum with specified byte order.""" if len(data) % 2 == 1: data = data + b'\x00' total = 0 for i in range(0, len(data), 2): if byte_order == 'big': word = (data[i] << 8) | data[i + 1] else: # little word = data[i] | (data[i + 1] << 8) total += word while total > 0xFFFF: total = (total & 0xFFFF) + (total >> 16) return total def byte_swap(value: int) -> int: """Swap bytes of a 16-bit value.""" return ((value & 0xFF) << 8) | (value >> 8) # Test datatest_data = bytes([0x45, 0x00, 0x00, 0x73, 0x00, 0x00, 0x40, 0x00]) sum_be = ones_complement_sum(test_data, 'big')sum_le = ones_complement_sum(test_data, 'little') print(f"Data: {test_data.hex()}")print(f"Big-endian sum: 0x{sum_be:04X}")print(f"Little-endian sum: 0x{sum_le:04X}")print(f"LE swapped: 0x{byte_swap(sum_le):04X}")print(f"BE == swap(LE): {sum_be == byte_swap(sum_le)}") # Complement (checksum)cs_be = (~sum_be) & 0xFFFFcs_le = (~sum_le) & 0xFFFFprint(f"Big-endian checksum: 0x{cs_be:04X}")print(f"Little-endian checksum: 0x{cs_le:04X}")print(f"Also byte-swapped: {cs_be == byte_swap(cs_le)}") # When we insert the checksum into the header (in network order)# and verify, both orderings produce 0xFFFFprint("--- Verification ---")# Insert big-endian checksum at positions 10-11header = bytearray(test_data + bytes([0x00, 0x00, 0xC0, 0xA8, 0x00, 0x01, 0xC0, 0xA8, 0x00, 0xC7]))# Compute actual checksum (pretend positions 8-9 are checksum field)# This is just illustrativeNetwork implementers don't need #ifdef for different architectures. The same C code computes correct checksums on big-endian SPARC, little-endian x86, and mixed-endian ARM. This was crucial for the early Internet's heterogeneous hardware environment.
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.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
"""Algebraic demonstration of checksum verification. Key identity: x + ~x = 0xFFFF in one's complement (negative zero)""" def oc_add(a: int, b: int) -> int: """One's complement 16-bit addition.""" result = a + b while result > 0xFFFF: result = (result & 0xFFFF) + (result >> 16) return result def oc_sum(words: list) -> int: """One's complement sum of a list of 16-bit words.""" total = 0 for w in words: total = oc_add(total, w) return total # Simulate sending data with checksumdata_words = [0x4500, 0x0073, 0x0000, 0x4000, 0x4011, 0xC0A8, 0x0001, 0xC0A8, 0x00C7] # Sender computes checksumdata_sum = oc_sum(data_words)checksum = (~data_sum) & 0xFFFF print("=== Sender Side ===")print(f"Sum of data words: 0x{data_sum:04X}")print(f"Checksum (~sum): 0x{checksum:04X}") # Verification: data_sum + checksum = ?verification = oc_add(data_sum, checksum)print(f"sum + checksum: 0x{verification:04X}")print(f"Is 0xFFFF? {verification == 0xFFFF}") # Receiver computes sum of all words including checksumall_words = data_words + [checksum]receiver_sum = oc_sum(all_words) print("=== Receiver Side ===")print(f"Sum of all words (including checksum): 0x{receiver_sum:04X}")print(f"Valid (== 0xFFFF): {receiver_sum == 0xFFFF}") # Demonstrate error detectionprint("=== Error Detection ===")corrupted_words = data_words.copy()corrupted_words[0] ^= 0x0001 # Single bit errorcorrupted_all = corrupted_words + [checksum]corrupted_sum = oc_sum(corrupted_all)print(f"Corrupted sum: 0x{corrupted_sum:04X}")print(f"Error detected: {corrupted_sum != 0xFFFF}")Alternative Verification Result:
Some implementations check for 0x0000 instead of 0xFFFF. Both are 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.
For verification, sum all words including the checksum. If the result (after folding) is 0xFFFF (or 0x0000 if you complement at the end), the checksum is valid. Avoid extracting the checksum separately unless necessary—the inclusive sum is simpler and less error-prone.
Programmers often ask: why not use simpler two's complement arithmetic for checksums? A detailed comparison illuminates the design decision.
| Property | One's Complement | Two's Complement |
|---|---|---|
| Negation | Bit inversion only (~x) | Bit inversion + add 1 (~x + 1) |
| Zero representations | Two (0x0000, 0xFFFF) | One (0x0000) |
| Overflow handling | End-around carry (add back) | Ignore carry (modulo 2^n) |
| Byte-order independence | Yes (critical for networking) | No (byte order matters) |
| Hardware today | Not native (emulated) | Native in all CPUs |
| Verification result | 0xFFFF if valid | Would vary by implementation |
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:
Little-endian:
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.
The Internet was built on heterogeneous hardware—VAX, PDP-11, Sun SPARC, Intel x86—with different byte orderings. One's complement made checksums work everywhere without architecture-specific code paths. This was essential for the early Internet's success.
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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
"""Efficient one's complement sum on modern two's complement hardware.""" def checksum_32bit_accumulator(data: bytes) -> int: """ Efficient implementation using a 32-bit accumulator. Key optimization: Defer all folding until the end. The 32-bit accumulator can hold the sum of up to 65535 16-bit words without overflow. """ if len(data) % 2 == 1: data = data + b'\x00' # 32-bit accumulator total = 0 # Sum all 16-bit words for i in range(0, len(data), 2): word = (data[i] << 8) | data[i + 1] total += word # Now fold 32 bits to 16 bits # First fold: add upper 16 bits to lower 16 bits total = (total >> 16) + (total & 0xFFFF) # Second fold: may have produced a carry total = (total >> 16) + (total & 0xFFFF) # Complement return (~total) & 0xFFFF def checksum_64bit_accumulator(data: bytes) -> int: """ Even more efficient using a 64-bit accumulator. Can process data in larger chunks (32 bits at a time) and defer all folding until the very end. """ if len(data) % 2 == 1: data = data + b'\x00' # 64-bit accumulator total = 0 length = len(data) i = 0 # Process 4 bytes (2 words) at a time when possible while i + 4 <= length: # Two 16-bit words combined words = (data[i] << 24) | (data[i+1] << 16) | (data[i+2] << 8) | data[i+3] # Add both words (treating as two separate 16-bit values) total += (words >> 16) + (words & 0xFFFF) i += 4 # Handle remaining 2 bytes if present while i + 2 <= length: word = (data[i] << 8) | data[i + 1] total += word i += 2 # Fold 64 bits to 32 bits total = (total >> 32) + (total & 0xFFFFFFFF) total = (total >> 32) + (total & 0xFFFFFFFF) # Fold 32 bits to 16 bits total = (total >> 16) + (total & 0xFFFF) total = (total >> 16) + (total & 0xFFFF) return (~total) & 0xFFFF # Verify both implementations produce same resulttest_data = b'The quick brown fox jumps over the lazy dog'cs_32 = checksum_32bit_accumulator(test_data)cs_64 = checksum_64bit_accumulator(test_data)print(f"32-bit accumulator: 0x{cs_32:04X}")print(f"64-bit accumulator: 0x{cs_64:04X}")print(f"Match: {cs_32 == cs_64}")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
The Linux kernel's optimized x86-64 checksum implementation achieves over 50 Gbps on modern CPUs. Python implementations are fine for learning but 100-1000x slower. For production, use library functions or hardware offload.
We've journeyed through the mathematical foundations of one's complement arithmetic and its application in the Internet checksum. Let's consolidate the essential knowledge:
Looking Ahead:
With the mathematical foundations solid, we can now examine the complete calculation process step by step. The next page walks through checksum computation in detail, showing exactly how to compute and verify checksums for IP, TCP, UDP, and ICMP.
You now understand one's complement arithmetic deeply: its representation, arithmetic operations, end-around carry, the negative zero concept, and why these properties made it ideal for the Internet checksum. This knowledge enables you to implement correct checksums and debug calculation issues.