Binary Representation Revisited — The Language of Low-Level Optimization

So far, we've discussed bits and binary primarily in terms of positive integers. But real-world computation requires negative numbers: bank balances can be overdrawn, temperatures can drop below zero, and game characters can move in negative directions.

The challenge is subtle but profound: bits have no inherent notion of 'negative.' A bit is either 0 or 1—there's no natural way to indicate that the value it contributes should be subtracted rather than added. Yet computers work with fixed-width bit patterns. How do we encode sign information within these constraints?

This page explores unsigned representation, the fundamental challenge of representing negatives, and the various schemes engineers have devised to solve this problem—culminating in two's complement, the universal standard.

Let's begin with the straightforward case: unsigned integers. These represent only non-negative values (0 and positive integers) and use all bits purely for magnitude.

For an n-bit unsigned integer:

• Minimum value: 0 (all bits zero)
• Maximum value: 2ⁿ - 1 (all bits one)
• Total values representable: 2ⁿ

The conversion between binary and decimal is straightforward positional notation:

Properties of unsigned integers:

1. Contiguous range: All values from 0 to 2ⁿ-1 are representable with no gaps.

2. Wrap-around on overflow: When an operation exceeds the maximum value, the result 'wraps around.' Adding 1 to 255 (in 8 bits) yields 0. This is mathematically equivalent to modular arithmetic: all operations are performed modulo 2ⁿ.

3. All bits are magnitude bits: There's no special interpretation of any bit position. Every bit contributes its power of 2 to the total.

4. Comparison is straightforward: Lexicographic comparison of bit patterns matches numeric comparison. The binary representation sorts in the same order as the numeric value.

Unsigned integers are ideal when values are inherently non-negative: array sizes, memory addresses, counts, hash values, and bit manipulation applications. Their simplicity and full utilization of the bit range make them the default choice when negatives aren't needed.

Many domains require negative values:

• Financial calculations: Account balances, profit/loss, debts
• Scientific computing: Temperatures, coordinates, derivatives
• Graphics and games: Positions, velocities, directions
• Algorithms: Deltas, differences, error terms

Without negative numbers, we'd need awkward workarounds: separate 'is negative' flags, biased representations, or parallel tracking of positive and negative components. These approaches are error-prone and complicate arithmetic.

The core challenge:

We have a fixed number of bits and need to represent both positive and negative values. If we have n bits, we can represent at most 2ⁿ distinct values. How do we divide these between positive and negative numbers?

There's no free lunch: if we allocate bit patterns to negative numbers, we must reduce the range of positive numbers. With 8 bits:

• Unsigned: 0 to 255 (256 values, all non-negative)
• Signed: typically -128 to 127 (256 values, split between negative and positive)

The question isn't whether to give up positive range—we must. The question is how to map bit patterns to negative values in a way that makes computation efficient.

The most intuitive approach to representing signed numbers is sign-magnitude representation. It directly mimics how we write negative numbers: a sign indicator followed by a magnitude.

The scheme:

• Most significant bit (MSB): Sign bit (0 = positive, 1 = negative)
• Remaining bits: Magnitude (absolute value)

For example, in 8-bit sign-magnitude:

Advantages of sign-magnitude:

1. Intuitive: Easy to understand; the magnitude is directly readable.
2. Simple negation: Just flip the sign bit.
3. Symmetric range: Same magnitude range for positive and negative.

Disadvantages of sign-magnitude (why it's not used):

Historical usage:

Despite these drawbacks, sign-magnitude appeared in early computers and still appears in IEEE 754 floating-point representation (where the sign, exponent, and mantissa are separate fields). For integers, however, the arithmetic complexity proved prohibitive, leading engineers to seek alternatives.

One's complement attempts to address sign-magnitude's arithmetic complexity. The key insight: define negation as bitwise complement—flip every bit.

The scheme:

• Positive numbers: Same as unsigned (MSB = 0)
• Negative numbers: Bitwise complement of absolute value (MSB = 1)
• Negation: Flip all bits

For example, in 8-bit one's complement:

How one's complement arithmetic works:

One's complement addition uses the same adder as unsigned addition, but with a twist: any carry-out from the MSB is added back to the result (called end-around carry).

Example: Adding 5 and -3 in 8-bit one's complement:

   00000101  (+5)
 + 11111100  (-3, which is complement of 00000011)
 ──────────
  100000001  (9 bits - there's a carry out)
        + 1  (add the carry back)
 ──────────
   00000010  (+2) ✓ Correct!

Advantages over sign-magnitude:

1. Simpler negation: Just flip all bits—a single NOT operation.
2. Uses standard adder: With end-around carry, the same adder works for signed and unsigned.
3. Symmetry: The range is symmetric around zero.

Remaining problems:

Before introducing two's complement, let's examine one more scheme: offset binary (also called excess-K or biased representation). This approach uses a different strategy altogether.

The scheme:

• Store the value V as the unsigned integer V + K, where K is a fixed offset (bias)
• Common choice: K = 2^(n-1) for n-bit representation

For 8-bit excess-128 (offset by 128):

Advantages of offset binary:

1. Unique zero: Only one representation of zero (the bit pattern for K).
2. Simple comparison: Unsigned comparison of bit patterns gives correct signed ordering.
3. Hardware-efficient comparisons: Use existing unsigned comparison circuits.
4. Full range: Uses all 2ⁿ values, no waste.

Disadvantages of offset binary:

Where offset binary is used:

Despite its arithmetic complexity, offset binary appears in:

1. IEEE 754 floating-point exponents: Exponents use excess-127 (single precision) or excess-1023 (double precision). This simplifies exponent comparison.

2. Audio processing: Digital audio sometimes uses offset binary for compatibility with older analog-to-digital converters.

3. Database ordering: Some databases use offset transformations to enable unsigned comparison of signed values.

For general-purpose integer arithmetic, however, the arithmetic complexity makes offset binary impractical. We need a scheme that works with standard adders—which brings us to two's complement.

Let's summarize the schemes we've examined before introducing two's complement. Understanding their trade-offs clarifies why two's complement ultimately won:

What we want:

The ideal scheme would have:

• ✅ A unique representation of zero
• ✅ Full range utilization (all 2ⁿ patterns used)
• ✅ Standard unsigned addition works for signed values
• ✅ Simple, consistent negation
• ✅ Efficient comparison
• ✅ No special cases or corrections needed

No scheme we've examined achieves all of these. Sign-magnitude and one's complement waste a bit pattern on negative zero. Offset binary requires arithmetic corrections. All three need special handling that complicates hardware.

Two's complement achieves all goals.

The next page develops two's complement in depth. Here, we'll preview why it succeeds where others failed:

You might wonder why we've spent so much time on signed representation. After all, many bit manipulation problems use unsigned integers. The answer: understanding representation avoids subtle bugs and unlocks techniques specific to signed values.

Common bug example:

Consider this code:

int array[10];
int index = -1;
if (index < sizeof(array)) {  // sizeof returns unsigned!
    // This branch is NOT taken on many platforms!
}

The comparison index < sizeof(array) compares a signed integer (-1) with an unsigned value (40 or 80, depending on pointer size). The signed -1 is converted to unsigned, becoming a very large positive number (e.g., 4294967295 on 32-bit). The comparison fails unexpectedly.

Understanding signed representation—specifically that -1 in two's complement is all-ones—explains this behavior and how to avoid it.

Let's consolidate what we've learned about representing positive and negative integers:

What's next:

With the stage set—understanding unsigned representation, the challenges of representing negatives, and the shortcomings of alternative schemes—we're ready for two's complement. The next page develops two's complement in full depth: its definition, properties, arithmetic behavior, and why it became the universal standard for signed integer representation.