Binary Representation Revisited - Learning Module

Loading content...

0/279

Two's Complement Intuition — The Universal Standard

The Elegant Solution

In the previous pages, we explored various schemes for representing signed integers—sign-magnitude, one's complement, and offset binary. Each had fundamental flaws: dual zeros, complex arithmetic, or correction requirements.

Two's complement resolves all of these issues with a single elegant insight. It became the universal standard for signed integer representation in the 1960s and remains unchallenged today. Every modern processor, programming language, and digital system uses two's complement for signed integers.

This page develops your intuition for two's complement—not just how it works mechanically, but why it works mathematically. This understanding transforms two's complement from a memorized rule into a tool you can reason about confidently.

What You Will Learn

By the end of this page, you will understand two's complement representation intuitively, know how to convert between decimal and two's complement, understand why standard addition works for signed values, and appreciate the properties that make two's complement ideal for bit manipulation.

The Core Insight — Giving the MSB Negative Weight

The genius of two's complement lies in a simple reinterpretation of the most significant bit (MSB). Rather than treating it as a sign flag or flipping its meaning, we assign it a negative weight.

In unsigned representation, all bits have positive weights:

Value = b₇×2⁷ + b₆×2⁶ + b₅×2⁵ + b₄×2⁴ + b₃×2³ + b₂×2² + b₁×2¹ + b₀×2⁰

In two's complement, the MSB contributes a negative power of 2:

Value = -b₇×2⁷ + b₆×2⁶ + b₅×2⁵ + b₄×2⁴ + b₃×2³ + b₂×2² + b₁×2¹ + b₀×2⁰

That's it. That single minus sign—making the MSB contribute -128 instead of +128—is the entire innovation.

twos_complement_examples.txt
8-bit Two's Complement Interpretation:
 
Positive Numbers (MSB = 0):
  00101010 = -0×128 + 32 + 8 + 2    = 0 + 42   = +42
  01111111 = -0×128 + 64+32+16+8+4+2+1 = 0 + 127 = +127
  00000001 = -0×128 + 1             = 0 + 1    = +1
 
Negative Numbers (MSB = 1):
  11111111 = -1×128 + 64+32+16+8+4+2+1 = -128 + 127 = -1
  10000000 = -1×128 + 0              = -128      = -128
  11010110 = -1×128 + 64+16+4+2      = -128 + 86 = -42
  10000001 = -1×128 + 1              = -128 + 1  = -127
 
Zero:
  00000000 = -0×128 + 0             = 0         = 0
  (Only ONE zero!)

Why this works:

The MSB's negative weight of -128 can be 'canceled out' by the positive bits, which can contribute up to +127. When MSB = 0, we get 0 to +127. When MSB = 1, we start at -128 and can add up to +127, giving -128 to -1.

Total range: [-128, +127] — all 256 patterns used, exactly one zero.

The elegant properties:

Unique zero: Only 00000000 = 0. The pattern 10000000 = -128, not -0.
Full range: With n bits, we represent -2^(n-1) to 2^(n-1)-1.
MSB indicates sign: If MSB = 0, the value is non-negative. If MSB = 1, negative. This is consistent but more nuanced than sign-magnitude.
Asymmetric range: There's one more negative value than positive (e.g., -128 exists but +128 doesn't). This asymmetry is inherent and important to remember.

The Mental Model

Think of the MSB as a 'debt' bit. When it's 1, you're in debt by -128. The other bits are your 'assets' that can pay off some of that debt. If assets (0-127) fully pay off the debt (-128), you'd be at exactly 0—but assets max out at 127, so with MSB=1, you remain at least -1 in debt.

Decimal to Two's Complement Conversion

There are several ways to convert decimal numbers to two's complement representation. Understanding multiple methods deepens intuition.

Converting positive decimals:

For non-negative values within range [0, 2^(n-1)-1], simply convert to binary as you would for unsigned:

Example: Convert +42 to 8-bit two's complement

42 ÷ 2 = 21 remainder 0  (LSB)
21 ÷ 2 = 10 remainder 1
10 ÷ 2 = 5  remainder 0
 5 ÷ 2 = 2  remainder 1
 2 ÷ 2 = 1  remainder 0
 1 ÷ 2 = 0  remainder 1  (stop when quotient = 0)

Read remainders bottom-to-top: 101010
Pad to 8 bits: 00101010

Verify: 32 + 8 + 2 = 42 ✓

Positive numbers look identical in unsigned and two's complement—the MSB is 0, so the negative weight contributes nothing.

Why Addition 'Just Works' — Modular Arithmetic

The most remarkable property of two's complement is that standard unsigned addition produces correct signed results. No special signed adder needed. Let's understand why.

The key insight: modular arithmetic

With n-bit fixed-width integers, all arithmetic is implicitly performed modulo 2ⁿ. The bit pattern 'wraps around' when it exceeds 2ⁿ.

Two's complement cleverly encodes negative numbers as their modular equivalents. In 8-bit arithmetic:

-1 ≡ 255 (mod 256), so -1 is represented as 11111111
-42 ≡ 214 (mod 256), so -42 is represented as 11010110

When we add these bit patterns using unsigned addition, the modular arithmetic gives us the correct signed result!

addition_example.txt
Example: 42 + (-1) in 8-bit two's complement
 
Signed interpretation:
  42 + (-1) = 41
 
Bit pattern addition (as if unsigned):
    00101010   (42)
  + 11111111   (-1, which is 255 unsigned)
  ──────────
  1 00101001   (297 in 9 bits)
    ────────
    00101001   (drop the carry = 41) ✓
 
The 'overflow' carry out is discarded, and we get 41!
 
──────────────────────────────────────────────────
 
Example: (-42) + (-3) in 8-bit two's complement
 
Signed interpretation:
  -42 + (-3) = -45
 
Bit pattern addition:
    11010110   (-42, which is 214 unsigned)
  + 11111101   (-3, which is 253 unsigned)
  ──────────
  1 11010011   (467 in 9 bits)
    ────────
    11010011   (drop carry = 211 unsigned = -45 signed) ✓
 
Verify: -128 + 64 + 16 + 2 + 1 = -128 + 83 = -45 ✓

The mathematical foundation:

For n-bit numbers, two's complement of a negative value x is defined as 2ⁿ + x (where x is negative, so this is 2ⁿ - |x|).

When we add a + b using bit patterns:

If both positive: straightforward addition
If one negative (say b < 0): we're computing a + (2ⁿ + b) = a + b + 2ⁿ. The 2ⁿ wraps around, leaving a + b.
If both negative: (2ⁿ + a) + (2ⁿ + b) = a + b + 2×2ⁿ. One 2ⁿ wraps, one produces a carry-out that we ignore.

In all cases, the n-bit result is a + b (mod 2ⁿ), which is exactly what we want.

This is why two's complement won:

The same adder circuit works for both signed and unsigned addition. No mode switching, no corrections, no special cases. Hardware designers rejoiced.

Subtraction for Free

Since negation in two's complement is simple (invert + add 1), subtraction a - b is just a + (-b). The same adder, with a negation step for b, handles subtraction. No separate subtractor needed.

Negation in Two's Complement

To negate a number in two's complement:

Invert all bits (bitwise NOT)
Add 1

Or use the rightmost-1 shortcut from earlier. Either way, negation is O(1).

Properties of two's complement negation:

Negation Properties

•Negation of 0 is 0 — Invert 00000000 → 11111111, add 1 → 00000000 (overflow discarded). Zero is its own negation.
•Negation is involution — Negating twice returns the original: -(-x) = x for all values except the minimum.
•The minimum value is self-negating — In 8-bit, negating -128 (10000000): invert → 01111111, add 1 → 10000000 = -128. The minimum value negates to itself!
•Why the minimum is special — There's no +128 in 8-bit two's complement (range is -128 to +127). The negation 'overflows' back to -128.
•Negation as 2ⁿ - x — Mathematically, the two's complement of x is 2ⁿ - x. For x = -128 in 8 bits: 256 - (-128) = 256 + 128 = 384 = 256 + 128, which wraps to 128... but we interpret 10000000 as -128, not +128.

negation_examples.txt
Negation Examples (8-bit):
 
Negate +1:
  00000001 → invert → 11111110 → add 1 → 11111111 = -1 ✓
 
Negate +127:
  01111111 → invert → 10000000 → add 1 → 10000001 = -127 ✓
 
Negate -1:
  11111111 → invert → 00000000 → add 1 → 00000001 = +1 ✓
 
Negate 0:
  00000000 → invert → 11111111 → add 1 → 00000000 = 0 ✓
  (The carry-out is discarded)
 
Negate -128 (the special case):
  10000000 → invert → 01111111 → add 1 → 10000000 = -128
  (Negating -128 gives -128 due to overflow)

The Minimum Value Trap

Be careful with INT_MIN (the most negative value). In many languages, -INT_MIN is undefined behavior or silently returns INT_MIN due to overflow. Always check for this edge case when negating or computing absolute values.

Detecting Signed Overflow

In unsigned arithmetic, overflow is detected by carry-out: if there's a carry beyond the MSB, the result 'wrapped around.'

In signed two's complement arithmetic, overflow detection is different. Carry-out doesn't determine signed overflow. Instead, we look at the sign bits.

Signed overflow occurs when:

Adding two positive numbers produces a negative result (crossed the positive boundary)
Adding two negative numbers produces a positive result (crossed the negative boundary)

Signed overflow does NOT occur when:

Adding numbers with different signs (result is between the operands; can't overflow)

Signed Overflow Detection Rules
A sign	B sign	Result sign	Overflow?
(0)	(0)	(0)	No
(0)	(0)	(1)	YES — positive overflow
(1)	(1)	(1)	No
(1)	(1)	(0)	YES — negative overflow
(0)	(1)	either	No (mixed signs can't overflow)
(1)	(0)	either	No (mixed signs can't overflow)

Formal rule:

Signed overflow occurs if and only if:

Sign of A = Sign of B, AND
Sign of Result ≠ Sign of A (equivalently, ≠ Sign of B)

In terms of bit operations:

overflow = (A_sign XOR Result_sign) AND (A_sign XNOR B_sign)
         = (A_sign XOR Result_sign) AND NOT(A_sign XOR B_sign)
         = ((A XOR Result) AND NOT(A XOR B)) >> (n-1)

This can be computed in constant time from the operands and result.

overflow_examples.txt
Overflow Examples (8-bit, range -128 to +127):
 
No overflow:
  50 + 75 = 125
  00110010 + 01001011 = 01111101
  Both positive, result positive ✓
 
Positive overflow:
  100 + 50 = 150... but 150 > 127!
  01100100 + 00110010 = 10010110
  Both positive, but result is negative (MSB=1)
  10010110 as signed = -128 + 16 + 4 + 2 = -106
  OVERFLOW! True result wrapped to -106.
 
Negative overflow:
  -100 + (-50) = -150... but -150 < -128!
  10011100 + 11001110 = 101101010 (9 bits)
  Drop carry: 01101010 = +106
  Both negative, but result is positive (MSB=0)
  OVERFLOW! True result wrapped to +106.

Carry vs Overflow

Carry-out and signed overflow are independent. You can have carry without overflow (valid negative subtraction), overflow without carry (adding two positive numbers past range), both, or neither. They serve different purposes for unsigned vs signed interpretation.

Sign Extension — Widening Signed Values

When converting a signed value to a wider type (e.g., 8-bit to 32-bit), we need to preserve its value and sign. This is done via sign extension: replicate the sign bit (MSB) into all the new high bits.

The rule:

If MSB = 0 (non-negative): pad with zeros
If MSB = 1 (negative): pad with ones

Both cases are the same rule: replicate the MSB.

sign_extension.txt
Sign Extension Examples (8-bit to 16-bit):
 
+42 (8-bit): 00101010
+42 (16-bit): 0000000000101010
  (pad with MSB's value: 0)
 
-42 (8-bit): 11010110
-42 (16-bit): 1111111111010110
  (pad with MSB's value: 1)
 
Verification that -42 is preserved:
  16-bit: -32768 + 16384 + 8192 + 4096 + 2048 + 1024 + 512 + 256
          + 128 + 64 + 16 + 4 + 2
        = -32768 + 32726 = -42 ✓
 
-1 (8-bit): 11111111
-1 (16-bit): 1111111111111111
  Value: -32768 + 32767 = -1 ✓

Why sign extension preserves value:

For a positive number, the MSB (sign bit) is 0. Adding more 0s to the left doesn't change the value—they contribute 0.

For a negative number in n bits with MSB = 1: the contribution is -2^(n-1). When we extend to m bits (m > n) with all 1s:

New contribution: -2^(m-1) + 2^(m-2) + 2^(m-3) + ... + 2^(n-1)
                = -2^(m-1) + (2^(m-1) - 2^(n-1))  [sum of geometric series]
                = -2^(n-1)  [same as original MSB contribution!]

The added 1-bits exactly cancel to maintain the original MSB's -2^(n-1) contribution.

Zero extension vs sign extension:

Zero extension: Always pad with 0s. Used for unsigned values.
Sign extension: Pad with the sign bit. Used for signed values.

Using the wrong extension corrupts the value. Zero-extending -1 (11111111) to 16 bits gives 0000000011111111 = +255, not -1.

Type Conversion Bugs

When casting between integer types in code, be aware of whether sign or zero extension applies. In C: casting signed char (-1) to int gives -1 (sign extended). Casting unsigned char (255) to int gives 255 (zero extended). The same bit pattern produces different results based on the source type's signedness.

Two's Complement and Bit Manipulation

Understanding two's complement unlocks several bit manipulation techniques that exploit signed representation properties:

Bit Manipulation Techniques Using Two's Complement

•Absolute value without branching — For signed x: (x ^ (x >> 31)) - (x >> 31) on 32-bit. The arithmetic right shift fills with sign bit, creating 0 or -1, enabling branchless absolute value.
•Extract the lowest set bit — x & (-x) gives a value with only the lowest set bit of x. Works because -x flips bits above the lowest 1, preserving only that bit when ANDed.
•Clear the lowest set bit — x & (x - 1) clears the lowest set bit. Useful for counting bits or detecting powers of 2.
•Set all bits below lowest set bit — x | (x - 1) fills in all bits below the lowest 1.
•Detect sign — Arithmetic right shift by n-1 gives -1 for negative, 0 for non-negative. This can be used for branchless conditionals.
•Negate conditionally — To negate based on a condition bit c: (x ^ -c) + c. If c=0, x unchanged. If c=1, inverts and adds 1 (negates).

twos_complement_tricks.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Absolute value without branching (32-bit signed)
int absolute_value(int x) {
    int mask = x >> 31;  // 0 if x >= 0, -1 if x < 0
    return (x ^ mask) - mask;
    // If x >= 0: (x ^ 0) - 0 = x
    // If x < 0:  (x ^ -1) - (-1) = (~x) + 1 = -x
}
 
// Extract lowest set bit
int lowest_set_bit(int x) {
    return x & (-x);
    // Example: x = 12 = 1100
    //         -x = 0100 (two's complement)
    //    x & -x = 0100 = 4 (lowest set bit)
}
 
// Check if power of 2 (using two's complement property)
bool is_power_of_two(int x) {
    return x > 0 && (x & (x - 1)) == 0;
    // (x - 1) flips all bits from lowest 1 down
    // If only one bit set, x & (x-1) = 0
}

These techniques leverage two's complement properties:

Negation inverts and adds 1, affecting bits predictably
-1 is all-ones, useful as a mask
Arithmetic right shift propagates sign, creating all-zeros or all-ones
The relationship between x, -x, and x-1 enables isolation and clearing of bits

We'll explore these and more in subsequent modules. For now, recognize that two's complement isn't just a representation detail—it's a tool for bit manipulation.

Summary: Two's Complement Mastery

Let's consolidate our understanding of two's complement:

Key Takeaways

•The core insight is negative weight — The MSB contributes -2^(n-1) instead of +2^(n-1). This single change enables all of two's complement's properties.
•Range is asymmetric — n bits represent [-2^(n-1), 2^(n-1)-1]. One more negative than positive. The minimum value has no positive counterpart.
•Unique zero — Only 00...0 is zero. No bit pattern is wasted on another zero representation.
•Standard addition works — The same adder circuit handles both signed and unsigned arithmetic due to modular arithmetic equivalence.
•Negation is simple — Invert all bits, add 1. Or use the rightmost-1 shortcut. O(1) operation.
•Overflow detection differs from carry — Overflow occurs when operands have the same sign but result has the opposite sign.
•Sign extension preserves value — Replicating the MSB when widening maintains the correct signed value.
•Two's complement enables bit tricks — Properties like -x inverting above lowest 1, and -1 being all-ones, power many bit manipulation techniques.

Module complete:

With this page, we've completed Module 1: Binary Representation Revisited. You now have a solid foundation in:

How Chapter 3's binary knowledge connects to bit manipulation
Bits as the hardware foundation of computation
Unsigned and signed integer representations
Two's complement: definition, properties, and implications

What's next:

Module 2 introduces bitwise operators — AND, OR, XOR, and NOT. These operators are the primitive tools from which all bit manipulation techniques are built. With your two's complement foundation, you'll understand not just what these operators do, but why their behaviors matter for signed and unsigned values.

Module Complete

Congratulations! You've completed Module 1: Binary Representation Revisited. You understand binary at both conceptual and hardware levels, can convert between decimal and two's complement, and know why two's complement became the universal standard. This foundation prepares you for the bitwise operators and manipulation techniques ahead.