Data Representation, Overflow and Binary Arithmetic (Cambridge IGCSE Computer Science 0478)
1. Number‑system refresher (Syllabus 1.1 – binary, decimal, hexadecimal)
All candidates must be able to convert between decimal, binary and hexadecimal and understand the relationship between bits, nibbles and bytes.
| Decimal | Binary (8‑bit) | Hexadecimal |
|---|
| 200 | 1100 1000₂ | C8₁₆ |
| 100 | 0110 0100₂ | 64₁₆ |
| 255 | 1111 1111₂ | FF₁₆ |
| 120 | 0111 1000₂ | 78₁₆ |
| ‑60 | 1100 0100₂ (two’s‑complement) | C4₁₆ |
| ‑80 | 1011 0000₂ (two’s‑complement) | B0₁₆ |
Why binary? Digital circuits have only two stable voltage levels – low (0 V) and high (5 V). Hexadecimal groups four bits, making long binary strings easier to read.
1.1 Bit‑, nibble‑ and byte‑hierarchy (Syllabus 1.2)
- 1 bit – the smallest unit (0 or 1).
- 1 nibble = 4 bits = one hexadecimal digit.
- 1 byte = 8 bits = two hexadecimal digits.
- 1 KB = 1 024 bytes, 1 MB = 1 024 KB, etc. (binary prefixes KiB, MiB are used in computing).
2. Two’s‑complement signed numbers (Syllabus 1.1)
- Positive numbers: ordinary binary, MSB = 0.
- Negative numbers: invert all bits and add 1.
- Range for an n-bit word: –2ⁿ⁻¹ → 2ⁿ⁻¹ – 1.
Examples (8‑bit):
+60 = 0011 1100₂
‑60 = 1100 0100₂ (invert 0011 1100 → 1100 0011, add 1 → 1100 0100)
+80 = 0101 0000₂
‑80 = 1011 0000₂ (invert 0101 0000 → 1010 1111, add 1 → 1011 0000)
3. Binary addition and overflow (Syllabus 1.1)
3.1 Unsigned overflow
When adding two unsigned numbers, overflow occurs if a carry out of the most‑significant bit (MSB) is produced. The extra bit is discarded, so the value stored in the register is wrong.
Example – add 200₁₀ and 100₁₀ in an 8‑bit unsigned register:
200₁₀ = 1100 1000₂
100₁₀ = 0110 0100₂
-----------------
Sum 1 0100 1100₂ (9 bits)
The left‑most ‘1’ is the carry‑out and is lost, leaving 0100 1100₂ = 76₁₀. The true sum is 300₁₀ → overflow.
3.2 Signed overflow (two’s‑complement)
For signed addition the overflow rule is slightly different:
- If the carry into the MSB differs from the carry out of the MSB, overflow has occurred.
- Equivalently: adding two numbers with the same sign produces a result with the opposite sign.
Example – add +120₁₀ and +100₁₀ (8‑bit two’s‑complement):
+120 = 0111 1000₂
+100 = 0110 0100₂
-----------------
Sum = 1101 1100₂ (MSB = 1 → interpreted as negative)
Both operands have sign 0, the result has sign 1 → overflow. The stored pattern represents ‑36₁₀, which is incorrect for the intended signed addition.
3.3 The Overflow Flag (V) and conditional branching (Syllabus 3.4)
Most CPUs have a status register that includes an Overflow Flag (V). After an arithmetic operation the ALU sets V = 1 if overflow occurred; otherwise V = 0. Programs can test V to decide whether to branch, e.g.:
ADD R1,R2 ; R1 ← R1 + R2
BOV LABEL ; branch if V = 1 (overflow detected)
4. Logical shifts (Syllabus 1.2)
Shifts move all bits left or right without regard to the sign bit. They are used for fast multiplication or division by powers of two.
| Operation | Binary before | Binary after | Decimal effect |
|---|
| Logical left shift << 1 |
0011 0101₂ |
0110 1010₂ |
×2 (5 → 10) |
| Logical right shift >> 1 |
1101 1000₂ |
0110 1100₂ |
÷2 (integer division, 216 → 108) |
If a ‘1’ is shifted out of the MSB the value is lost – effectively an overflow for the shifted result.
5. Data transmission and error detection (Syllabus 2)
- Packet structure: header (address, length, control), payload (data), trailer (checksum, CRC).
- Parity bit: simple error‑detection; adds 1 if the number of 1‑bits is odd (odd parity) or even (even parity).
- Checksum: sum of all payload bytes using unsigned binary addition. Because the addition is performed in a fixed‑size word (usually 8‑ or 16‑bits), overflow must be handled – the carry out is wrapped around (one’s‑complement addition) or discarded (two’s‑complement). Incorrect handling gives a wrong checksum and the receiver will reject the packet.
- ARQ (Automatic Repeat reQuest): if a checksum fails, the receiver asks the sender to retransmit.
5.1 Why overflow matters for checksums
When a large file is divided into 8‑bit blocks, the sum may exceed 255. The ALU discards the carry‑out, and the remaining 8‑bit value is stored as the checksum. If a program forgets to wrap the carry, the transmitted checksum will not match the receiver’s calculation, causing a transmission error.
6. Hardware overview (Syllabus 3)
6.1 CPU components relevant to overflow
- Registers: small, fast storage inside the CPU.
- Program Counter (PC) – holds address of next instruction.
- Memory Address Register (MAR) – holds address of memory location being accessed.
- Memory Data Register (MDR) – holds data read from or written to memory.
- Accumulator (ACC) – often used for arithmetic results.
- Status/Flag Register – contains Zero (Z), Carry (C), Overflow (V), Sign (S) flags.
- ALU (Arithmetic‑Logic Unit): performs binary addition, subtraction, logical operations, sets the flag bits.
- Buses: address bus (carries memory addresses), data bus (carries the actual bits), control bus (carries read/write signals, clock).
- Cache: small, fast memory close to the CPU that stores recently used data to reduce main‑memory accesses.
6.2 Storage hierarchy (Syllabus 1.3)
| Level | Typical device | Typical size | Typical speed |
|---|
| Registers / Cache | CPU registers, L1/L2 cache | KB | nanoseconds |
| Primary memory | RAM (DRAM) | GB | tens of nanoseconds |
| Secondary storage | SSD, HDD | TB | micro‑ to milliseconds |
| Archival | Optical disc, magnetic tape | TB | seconds to minutes |
6.3 Network hardware (Syllabus 2.4)
- NIC (Network Interface Card): converts parallel data from the CPU into serial bits for the network medium.
- Switch/Router: forwards packets based on MAC (layer 2) or IP (layer 3) addresses.
- MAC address: 48‑bit hardware identifier; used in Ethernet frames.
- IP address: 32‑bit (IPv4) logical address for routing across networks.
7. Software context (Syllabus 4)
- System software: operating system (OS) manages hardware resources, provides file systems, handles interrupts, and performs context switching.
- Application software: programs written to solve specific user problems (e.g., word processors, browsers).
- Interrupts: hardware or software signals that temporarily halt the CPU’s current instruction flow, save its state, and jump to an interrupt‑service routine. The OS uses interrupts for I/O, timers, and error handling (including overflow detection).
- High‑level languages: translate human‑readable code into machine code; the compiler/assembler must generate correct instructions to test the overflow flag when required.
8. Summary checklist – detecting overflow
- Identify the word size n (e.g., 8 bits).
- Know the representation:
- Unsigned range: 0 → 2ⁿ − 1.
- Signed two’s‑complement range: –2ⁿ⁻¹ → 2ⁿ⁻¹ − 1.
- Perform binary addition, writing down carries for each column.
- Unsigned overflow: a carry out of the MSB means overflow.
- Signed overflow: if the carry into the MSB ≠ the carry out of the MSB, or if two numbers with the same sign produce a result with the opposite sign.
- The CPU sets the Overflow Flag (V). Use a conditional branch (e.g.,
BOV) if the program must react.
9. Practice questions (exam style)
- In an 8‑bit unsigned system, add 150₁₀ and 120₁₀. State whether overflow occurs and give the stored 8‑bit result.
- In an 8‑bit two’s‑complement system, add ‑60₁₀ and ‑80₁₀. Detect overflow and write the binary pattern that would be stored.
- Explain why adding 1 to the maximum unsigned 8‑bit value 255₁₀ causes overflow.
- Show the result of a logical left shift of
0010 1101₂ by one position. Does this operation produce an overflow?
- A file is transmitted as a series of 8‑bit bytes. The sender computes a checksum by adding all bytes using unsigned 8‑bit addition and discarding any carry‑out. The receiver obtains a different checksum. List two possible reasons related to overflow.
10. Answers – teacher reference
-
150 = 1001 0110₂
120 = 0111 1000₂
Sum = 1 0000 1110₂ (9 bits)
Carry‑out of MSB = 1 → overflow.
Stored 8‑bit result = 0000 1110₂ = 14₁₀.
-
-60 = 1100 0100₂
-80 = 1011 0000₂
Sum = 1 0111 1100₂ (9 bits)
Carry into MSB = 0, carry out = 1 → overflow.
Stored pattern = 0111 1100₂ = 124₁₀ (interpreted as positive, which is wrong for signed arithmetic).
-
Maximum unsigned 8‑bit value:
1111 1111₂ = 255₁₀.
Adding 1 gives 1 0000 0000₂ (9 bits). The extra MSB is discarded, leaving 0000 0000₂ = 0₁₀. The stored value does not equal the mathematical result → overflow.
-
0010 1101₂ << 1 = 0101 1010₂
The bit shifted out of the MSB is 0, so no overflow occurs. The numeric value doubles: 45₁₀ → 90₁₀.
-
- One or more intermediate sums produced a carry‑out that was not wrapped around (i.e., the implementation treated the addition as signed rather than unsigned).
- The receiver used a different word size (e.g., 16‑bit addition) or a different end‑ianness, causing the final 8‑bit checksum to differ.