Computer architecture

Lesson 1 of 81945–today7 min

Number systems and two's complement

On 4 June 1996 the first Ariane 5 rocket veered off course about 37 seconds after its main engine ignited and was destroyed. The inquiry board traced the loss to the inertial reference software: converting a value called the horizontal bias from floating point to an integer raised an operand error, and both the active and the backup unit shut down for the same reason.

The conversion went from a 64-bit floating-point number to a 16-bit signed integer, which can hold nothing above 32,767. The faster Ariane 5 produced values that Ariane 4 never had. Knowing how many values a pattern of bits can hold is not trivia.

Positional notation in any base

In base b, a digit's value is the digit times b raised to its position, counting from 0 on the right. 2D in hexadecimal is 2 × 16 + 13 = 45; 101101 in binary is 32 + 8 + 4 + 1 = 45. Computers store binary because a circuit with two stable states is cheap and reliable. Humans read binary through hexadecimal, because one hex digit is exactly four bits (a nibble): 0010 1101 is 0x2D at a glance. Octal groups three bits and survives in Unix permissions (chmod 755). To convert decimal to binary, divide by 2 repeatedly and read the remainders from bottom to top, or subtract the largest powers of two that fit. With n bits you can represent 2ⁿ different patterns: 256 for a byte, about 4.29 billion for 32 bits.

0 to 65,535

1100C
1010A

Bit weights: … 128 · 64 · 32 · 16 · 8 · 4 · 2 · 1

−202 in 8-bit two's complement: only for 1 to 128

One value in binary, octal, decimal and hexadecimal. Edit any of them and the others follow.

Negative numbers: two's complement

Every mainstream processor stores signed integers in two's complement. With n bits, the most significant bit has weight −2ⁿ⁻¹ instead of +2ⁿ⁻¹, and the rest keep their usual positive weights. An 8-bit signed integer therefore ranges from −128 (10000000) to +127 (01111111), and a 16-bit one from −32,768 to +32,767. To negate a number, invert every bit and add 1. The design has three advantages over sign-and-magnitude: there is a single zero, the leading bit still tells the sign, and the same adder circuit adds signed and unsigned numbers. Subtraction becomes adding the negation. Widening a value to more bits copies the sign bit to the left (sign extension): −3 is 11111101 in 8 bits and 1111111111111101 in 16.

Overflow happens when the true result does not fit. For unsigned addition, it shows as a carry out of the top bit. For signed addition, it happens only when two operands of the same sign give a result of the opposite sign; the carry out alone does not tell you. Processors set separate flags for the two cases (carry and overflow on x86 and ARM), and the program must check the right one.

Worked exercise

Encoding −45 and an 8-bit overflow

(a) Write 45 in binary and hexadecimal. (b) Encode −45 as an 8-bit two's complement integer and verify it. (c) Add 100 and 50 as 8-bit signed integers. What bit pattern results, how is it read, and why?

Try it first, then reveal the solution one step at a time.

python
def to_signed(x, bits=8):
    # reinterpret an unsigned bit pattern as two's complement
    return x - (1 << bits) if x & (1 << (bits - 1)) else x

pattern = -45 & 0xFF          # keep the low 8 bits
print(bin(pattern), hex(pattern))   # 0b11010011 0xd3
print(to_signed(pattern))     # -45
print(to_signed((100 + 50) & 0xFF))   # -106: overflow
print(int('2D', 16), int('101101', 2), oct(45))   # 45 45 0o55
Python integers never overflow, so masking with 0xFF imitates an 8-bit register.

Key terms

Hexadecimal
Base 16; each digit stands for exactly four bits.
Two's complement
Signed encoding in which the top bit weighs −2ⁿ⁻¹; negate by inverting and adding 1.
Sign extension
Copying the sign bit into the new high bits when a signed value is widened.
Overflow
A result too large or too small for the number of bits; for signed addition, same-sign inputs and an opposite-sign result.
Nibble
Four bits, one hexadecimal digit.

Check what you learned

  1. 1.What is the range of a 16-bit two's complement integer?

  2. 2.Which 8-bit pattern encodes −1 in two's complement?

  3. 3.In 8-bit signed arithmetic, which addition overflows?

Practise it for the exam

Sources