Computer architecture begins with a contract about bits. A wire carries one of two reliably distinguishable signal ranges, but the signal itself is not intrinsically an integer, character, address, instruction, or color. Meaning is assigned by an encoding, and every later layer—from an arithmetic unit to a compiler, debugger, file format, and network protocol—must preserve that agreement. A systems architect therefore asks two questions for every bit pattern: “What representation is being assumed?” and “Which operations preserve its intended meaning?”
This chapter develops the representations used by a small processor. It treats unsigned and signed fixed-width integers as algebraic systems, derives two’s-complement operations instead of presenting them as a memorized trick, analyzes overflow and widening, and then turns to IEEE-style floating-point numbers. The final section connects representation choices to instruction behavior, C language semantics, serialization, and testing. The examples are deliberately finite: a 4-bit or 8-bit machine makes the wraparound visible, while the same proofs scale to 32- and 64-bit words.
Bits, words, and interpretation
A bit is an element of the set A -bit word is an element of If the bits are written from most significant to least significant as the conventional unsigned interpretation is
The function is a bijection from bit strings to the integers in Thus an unsigned 4-bit word has sixteen possible values, from 0000 through 1111, and no 4-bit pattern can represent 16. This is not a weakness of binary notation; it is a consequence of the finite state space. The processor must define what happens when an operation mathematically asks for a value outside the representable set.
The same word can have several meanings. 01000001 is 65 as an unsigned integer, 65 as a two’s-complement integer, the ASCII character A under one character encoding, or an opcode under a particular ISA. The bits do not carry their own type. A type is a promise made by the surrounding computation, and a bug often consists of applying an operation belonging to one promise to data governed by another.
The term word is architectural rather than universal. An ISA may define 32-bit general-purpose registers while an implementation internally uses wider physical values. Memory is usually byte-addressed, so a 32-bit word occupies four consecutive bytes, but the byte order must also be specified. In little-endian order, the least significant byte occupies the lowest address; in big-endian order, the most significant byte does. Endianness does not change the numerical value when the bytes are reassembled correctly, but it changes the byte sequence exposed to a debugger, file format, or network peer.
Worked example: reconstructing a word. Suppose the four bytes at increasing addresses are 78 56 34 12. Interpreted as little-endian hexadecimal, they form 0x12345678; interpreted as big-endian, they form 0x78563412. A memory dump is therefore incomplete without the byte-order convention. The error is not arithmetic—the reader has used the wrong reconstruction function.
Bit Pattern Interpretation Matrix
Evaluate each statement regarding how bit patterns, types, and word representations function in computer architecture:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Unsigned arithmetic is modular arithmetic
The hardware adder has a fixed number of output wires. If it adds two -bit operands, the low output bits are naturally the residue modulo a possible carry-out is an additional bit and is not part of the -bit result unless the ISA explicitly exposes it. Thus fixed-width unsigned addition implements
For 4-bit words, produces a low result of 0000 and a carry-out of 1. Numerically, but the 4-bit result represents This is wraparound, not a claim that 15 and 1 sum to 0 in the integers. It is the behavior of the projection from an unbounded mathematical result into a finite ring.
Subtraction can use the same adder. In modular arithmetic, the additive inverse of modulo is The circuit computes as with the same low-bit projection. For example, on 8 bits, the inverse of 3 is 253 because Subtracting 3 from 5 becomes
Multiplication is also modular when only the low bits are retained. A full multiplier may produce a -bit product, and some instructions return both halves; an ordinary fixed-width multiply commonly returns the low half. The distinction matters for overflow detection, cryptographic arithmetic, array-size calculations, and compiler optimizations.
Carry versus overflow. For unsigned addition, the carry-out is the natural overflow indicator: the mathematical sum exceeds exactly when a carry leaves the top bit. For signed two’s-complement addition, carry-out alone is not the right test. Signed overflow occurs when two operands with the same sign produce a result with the opposite sign. Equivalently, for addition, overflow is the exclusive-or of the carry into and carry out of the sign bit. The two predicates answer different questions because unsigned and signed interpretations assign different meanings to the same bit pattern.
Worked example: 8-bit addition. Consider 01111111 + 00000001. As unsigned values, this is which is representable, so there is no unsigned carry-out. As signed two’s-complement values, the operands are and but the result pattern 10000000 represents The mathematical signed result 128 is outside the signed range so signed overflow occurred. A processor may set a signed-overflow flag, an unsigned-carry flag, both, or neither depending on the ISA; software must use the flag whose definition matches the intended type.
The bits need an interpretation
An eight-bit adder produces 10001100 from 01111000 + 00010100. One report calls the result 140; another calls it -116 and flags overflow.
Which statements correctly explain why these two reports differ without changing the output bits?
Signed integers and two’s complement
Two’s-complement representation defines the signed interpretation
The top bit has negative weight, while all lower bits retain positive powers of two. The representable range is
There is one representation of zero, 000...000. The asymmetry—one more negative value than positive value—is forced by using one of the patterns for each integer and reserving the sign bit as a negative weight. For 8 bits, the range is 11111111 is 10000000 is and 01111111 is
To encode a negative integer where compute In bit terms, invert every bit of the positive representation and add one. For on 8 bits, 00000101 becomes 11111010 after inversion and 11111011 after adding one; interpreted modulo 256 is The reason this procedure works is algebraic: so the bit pattern is the additive inverse of in the fixed-width ring.
The two’s-complement sign rule is therefore not an independent arithmetic system bolted onto a binary adder. Signed addition can use the same modular addition as unsigned addition. If the mathematical signed result lies in range, the modular result has the correct signed interpretation. If it lies outside range, the bits still form a residue, but the signed interpretation is not the intended integer result; that is precisely overflow.
Worked example: on 8 bits. Encode as 11111010 and 9 as 00001001. Add:
11111010
+ 00001001
--------
00000011
The result is 00000011, or 3. Both operands have different signs, so signed overflow is impossible: adding a positive and a negative value cannot exceed both ends of the signed interval in one step. This is a useful mental check, but the bit-level overflow predicate remains the authoritative one.
Predict the unsigned and signed interpretations of input 128 at width 8, then change the width to 9. The mathematical input is unchanged: only the projection and interpretation change. Width 8 yields unsigned 128 and signed −128; width 9 yields 128 under both interpretations because its sign bit is now zero.
Expose fixed-width overflow
Change the mathematical input and word width. The hardware keeps the residue; signed interpretation changes at the sign boundary.
Model scope: residue modulo 2^w and two's-complement decoding; language-level undefined behavior and floating point are deliberately excluded.
Static state: 8-bit 127 is representable under both unsigned and two's-complement interpretations; adding one crosses the signed boundary.
Sign extension, zero extension, and truncation
Changing width is not a neutral operation. To preserve an unsigned value when moving from to bits, prepend zeros; this is zero extension. To preserve a two’s-complement signed value, replicate the sign bit; this is sign extension. For example, the 8-bit signed value 11110110 is Sign-extending to 16 bits gives 11111111 11110110, which is still Zero-extending it gives 00000000 11110110, which is 246.
The same bit pattern can therefore change value solely because the type used for extension changed. This is a common source of security bugs when a signed length or index is converted to an unsigned size before bounds checking. In a C-like language, the expression’s usual arithmetic conversions may perform an implicit conversion that makes a negative value appear very large. A safe design makes the domain and conversion explicit, checks the sign before conversion, and checks multiplication or addition for range overflow before allocating or indexing.
Truncation from bits to bits discards high bits and preserves the result modulo It does not generally preserve a signed value. For example, 16-bit 00000000 10000000 is 128, while truncating to 8 bits gives 10000000, which is -128 under two’s complement. Truncation is safe only when the discarded bits are known to be redundant for the target interpretation: all zero bits for an unsigned value, or all copies of the sign bit for a signed value.
Exercise with solution outline. A 16-bit register contains 0xFF80. Interpret it as signed, sign-extend it to 32 bits, zero-extend it to 32 bits, and truncate the original bit pattern to 8 bits.
The 16-bit signed value is because the bit pattern is Sign extension produces 0xFFFFFF80, still Zero extension produces 0x0000FF80, which is 65408 as an unsigned 32-bit value. Truncation produces 0x80; that is 128 unsigned or -128 signed. The final answer is intentionally two-valued until the target type is named.
Shifts and bit fields
Logical left shift by positions multiplies an unsigned value by modulo when bits shifted out are discarded. Logical right shift inserts zeros and computes floor division by for an unsigned value. Arithmetic right shift inserts copies of the sign bit and approximates division by a power of two for negative two’s-complement values, but the exact rounding rule must be specified by the ISA.
Bit fields use masks and shifts to pack several logical values into one word. To extract a field occupying bits through compute
To insert a new unsigned field value first validate clear the destination bits with the complement of the mask, then OR in Validation is essential: silently truncating a field can turn a valid identifier into a different identifier.
Worked example: a packed control word. Let bit 0 be enabled, bits 1–3 be a mode in the range 0–7, and bits 4–7 be a priority in the range 0–15. For word 10110101, enabled=1; extracting mode gives (0xB5>>1)&0x7 = 2; extracting priority gives (0xB5>>4)&0xF = 11. To set mode to 6, clear mask 0x0E and insert 6<<1, obtaining 0xBD. The operation preserves all bits outside the mode field by construction.
Code Exercise
Pack and extract bit fields without clobbering neighbors
Complete the bitwise expressions to extract the 3-bit mode field (bits 1..3) and update it to a validated new mode while preserving bit 0 (enabled) and bits 4..7 (priority).
uint8_t extract_mode(uint8_t word) { return (word >> ) & ; } uint8_t update_mode(uint8_t word, uint8_t new_mode) { assert(new_mode < 8); return (word & ~( << 1)) | (new_mode << ); }
Verify two's-complement sign extension and overflow predicates
Bit-field layout creates an interface boundary. A producer and consumer must agree on width, signedness, reserved values, byte order, and whether unknown bits must be zero. The safest parser rejects impossible encodings rather than treating reserved patterns as future-compatible by accident.
Fixed-point and floating-point numbers
Fixed-point representation allocates a fixed number of fractional bits. With fractional bits, an integer storage value represents It gives uniform spacing and predictable integer operations, which is valuable in embedded control and financial formats, but its range and precision are fixed globally. Multiplying two values with fractional bits produces a value scaled by and requires a rescaling shift, with rounding policy made explicit.
Floating point instead represents values approximately as
where the sign significand and exponent are encoded in finite fields. IEEE 754 binary formats use normalized numbers with a biased exponent, subnormal numbers near zero, signed zero, infinities, and NaNs. The details matter because floating-point arithmetic is not ordinary real arithmetic: addition is not associative, overflow can produce infinity, and an invalid operation can produce NaN.
For a normalized binary format with precision adjacent values within one exponent bin differ by a fixed unit in the last place (ULP). Relative spacing is approximately constant within the normal range, while absolute spacing grows with magnitude. Near zero, subnormals provide gradual underflow with a fixed smaller spacing until the representation reaches zero.
Worked example: why 0.1 is not exact in binary. A finite binary fraction has the form If had such a form, then giving The left side is divisible by 5 while the right side is not, so no such integers exist. A binary floating-point format must round 0.1 to a nearby representable value. Repeated addition of that approximation can accumulate error, and comparing a computed value directly with a decimal expectation can fail.
Rounding modes define how an exact result between representable numbers is chosen. Round-to-nearest, ties-to-even is common because it avoids a systematic upward bias in repeated operations. Even with this mode, cancellation can destroy significant digits: subtracting two nearly equal large values removes the leading digits that carried reliable information and leaves mostly rounding noise.
Numerical stability is therefore an architectural concern as well as a mathematical one. A program that sums a long sequence should consider pairwise summation, compensated summation, or a wider accumulator when the error budget requires it. A processor’s floating-point unit implements specified operations and rounding, but it cannot infer the application’s acceptable error or replace an error analysis.
Representation at software boundaries
The representation contract becomes especially fragile at boundaries. A memory-mapped device may define bit 7 as a write-one-to-clear status flag, so a read-modify-write intended to update bit 0 can accidentally clear an event. A file format may store a 32-bit length in network byte order, while the host CPU is little-endian. A compiler may assume signed overflow is impossible in a language mode where the programmer expected modular wraparound. A cryptographic protocol may require canonical serialization so that two byte strings cannot encode the same signed message.
The remedy is not “be careful” but to define boundary functions. A decoder should accept bytes, validate length and reserved fields, and return a typed value or an error. An encoder should reject values outside field ranges. Arithmetic that can cross a representational boundary should use checked, saturating, or explicitly modular operations according to the requirement. Tests should include the minimum, maximum, zero, sign transition, one-past-the-end, endian reversal, NaN, infinity, and malformed encodings where applicable.
Worked boundary example. Suppose an image header contains width and height as unsigned 32-bit values, followed by width*height*4 bytes of pixels. If the multiplication is performed in a 32-bit type, dimensions such as 70,000 by 70,000 wrap before allocation. A later write based on the mathematical product can overflow the allocated buffer. A safe decoder first checks each dimension against a policy limit, promotes to a wider type, checks width <= SIZE_MAX/(height*4), and only then allocates. The representation lesson is that the bit width of an intermediate expression is part of the security proof.
Summary of invariants
Core representation invariants and failure modes:
| Invariant | Mathematical condition | Hardware mechanism | Concrete failure mode when violated |
|---|---|---|---|
| 1. Unsigned residue | Discard carry-out bit | Image buffer size calculation wraps to small value before allocation | |
| 2. Two’s-complement | MSB carries negative weight | Negating the minimum value produces | |
| 3. Extension safety | Replicate MSB for signed; zero-pad unsigned | Zero-extending negative signed index creates giant unsigned offset | |
| 4. Overflow vs carry | Distinct CPU flags (CF vs OF) | Using unsigned carry (CF) to check signed overflow (OF) | |
| 5. Floating point | Finite binary approximations | IEEE 754 round-to-even and exception flags | Associativity failure in summation; non-exact representation of 0.1 |
| 6. Boundary contracts | Canonical serialization | Strict validation before field packing | Truncation silently aliases reserved bitfields to valid identifiers |
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 1.1.1: Two's-Complement Arithmetic and Overflow Flags
A 5-bit two’s-complement machine adds 10110 and 01011. Decode both operands, compute the bit result, decide whether signed overflow occurred, and decide whether unsigned carry occurred.
HintExpandCollapse
Recall that signed overflow detects whether the mathematical sum falls outside the 5-bit signed range [-16, 15], while unsigned carry checks whether the sum exceeds 31.
Worked solutionExpandCollapse
10110 is and 01011 is 11. The mathematical sum is 1, so the result is 00001 with no signed overflow. As unsigned values, the operands are 22 and 11, whose sum 33 is outside the 5-bit unsigned range 0–31; the low result is 1 and carry-out is 1. This contrast is the point: one bit computation supports two different overflow predicates.
Exercise 1.1.2: Bitfield Masks and Extraction
A 12-bit word stores a 3-bit tag at bits 9–11, a 5-bit length at bits 4–8, and a 4-bit flags field at bits 0–3. Give masks and extraction expressions for each field. What must be checked before inserting a length of 31?
HintExpandCollapse
Construct each mask with 1s at designated positions in hex. Extract with bitwise AND followed by right-shift by the field's starting index. Compare 31 against the 5-bit maximum capacity.
Worked solutionExpandCollapse
The tag mask is 0xE00, the length mask is 0x1F0, and the flags mask is 0x00F; extraction shifts the masked value right by 9, 4, or 0 respectively. Length 31 fits the five-bit field exactly; length 32 does not and must be rejected rather than truncated to zero.
Exercise 1.1.3: Sign Extension Safety at Boundaries
Explain why zero-extending a negative 8-bit array index before checking it against an unsigned array length can be dangerous. Give a safe sequence of checks.
HintExpandCollapse
Trace what value -1 becomes when zero-extended versus sign-extended into a 32-bit or 64-bit unsigned type.
Worked solutionExpandCollapse
A negative signed index such as -1 becomes a very large unsigned value after conversion, potentially passing a poorly ordered comparison or changing which comparison is performed. First verify that the signed index is nonnegative, then convert to an unsigned size type, then compare against the array length, and only then calculate the address.
Exercise 1.1.4: Floating-Point Precision and Relative Spacing
Derive the maximum relative spacing in a normalized binary floating-point format with precision under round-to-nearest, ignoring subnormals. State the assumption about the exact value’s location between adjacent representable numbers.
HintExpandCollapse
In a binade [2^e, 2^(e+1)), adjacent normalized values are spaced by 2^(e - p + 1). Relate the half-ULP maximum rounding error to the binade's lower endpoint.
Worked solutionExpandCollapse
In a binade, adjacent normalized values are separated by The relative gap to the lower value is therefore Round-to-nearest makes the maximum rounding error half an ULP, at most relative to a value near the lower endpoint; the exact bound varies slightly across the binade. The assumption is that the exact value is rounded to the nearest representable neighbor, not truncated.
Exercise 1.1.5: Canonical Serialization Design
Design a byte-level serialization for a signed 24-bit integer. Specify byte order, encoding range, and the decoder’s response to out-of-range or noncanonical encodings.
HintExpandCollapse
Specify an exact 3-byte layout (e.g. little-endian two's complement), write down the explicit range [-2^23, 2^23 - 1], and state parser rejection rules for malformed lengths.
Worked solutionExpandCollapse
A 24-bit signed two’s-complement value ranges from through Encode its modular 24-bit pattern, choose big- or little-endian order, and require the decoder to sign-extend bit 23. A canonical decoder rejects a byte sequence of the wrong length and any alternate encoding not allowed by the format rather than silently accepting ambiguous representations.