Perform binary addition and subtraction

1.1 Data Representation – Cambridge A‑Level Computer Science (9618)

Learning Objectives

• Perform binary addition and subtraction (direct borrow and two’s‑complement).
• Convert between binary, decimal, hexadecimal and BCD.
• Understand binary prefixes (IEC) and how they differ from SI prefixes.
• Detect overflow and under‑flow for both unsigned and signed arithmetic.
• Explain why two’s‑complement is the standard signed representation in hardware.
• Identify the purpose of ASCII, extended ASCII and Unicode character encodings.

1. Number‑System Overview

1.1 Binary ↔ Decimal ↔ Hexadecimal Conversions

• Binary → Decimal: multiply each bit by 2ⁿ (n = position from right, starting at 0) and sum.
• Decimal → Binary: repeatedly divide by 2, recording remainders (or use powers of 2).
• Binary → Hexadecimal: group binary digits in sets of four (starting from the right) and replace each group with its hex equivalent.
• Hexadecimal → Binary: replace each hex digit with its 4‑bit binary pattern.

1.2 BCD Conversion Example

Decimal 27 → BCD (packed):

1. Separate each decimal digit: 2 and 7.
2. Convert each digit to a 4‑bit binary nibble: 2 → 0010, 7 → 0111.
3. Combine the nibbles: 0010 0111.

1.3 Binary Prefixes (IEC) vs. SI Prefixes

Example: 1 MiB = 2²⁰ bytes = 1 048 576 bytes, whereas 1 MB (SI) = 10⁶ bytes = 1 000 000 bytes. The IEC prefixes remove the ambiguity that can arise when manufacturers use SI prefixes for memory.

2. Binary Addition

2.1 Addition Rules (Truth Table)

2.2 Step‑by‑Step Example (Unsigned)

Add 1011₂ + 0110₂ (4‑bit words):

1 0 1 1
+ 0 1 1 0
----------
Carry: 1 1 0 0
Result:1 0 0 0 1

Result = 10001₂ (decimal 17). The extra carry indicates unsigned overflow for a 4‑bit register.

2.3 Overflow Detection

• Unsigned addition: overflow occurs when a carry is generated out of the most‑significant bit (MSB).
• Signed (two’s‑complement) addition:

  • Let C_in be the carry into the sign bit and C_out the carry out of the sign bit.
  • Overflow = C_in ⊕ C_out (XOR). If they differ, the signed result cannot be represented.

2.4 Signed‑Overflow Example

8‑bit signed addition: 0110 1101₂ (109) + 0101 0011₂ (83)

0 1 1 0 1 1 0 1
+ 0 1 0 1 0 0 1 1
-----------------
1 0 0 0 0 0 0 0

• Carry into the sign bit = 0, carry out = 1 → XOR = 1 → signed overflow.
• Correct 8‑bit two’s‑complement result is 1000 0000₂, which represents –128, not the expected +192.

3. Binary Subtraction

3.1 Direct Borrow Method

Borrow works exactly as in decimal, but a borrow means “take 2” from the next higher bit.

Example: 10101₂ – 00111₂

1 0 1 0 1
- 0 0 1 1 1
------------
0 1 1 1 0   (binary 14)

3.2 One’s‑Complement Subtraction (Unsigned)

1. Form the one’s complement of the subtrahend (invert every bit).
2. Add this to the minuend.
3. If a carry out of the MSB occurs, perform an end‑around carry by adding that carry back to the LSB.

Works for unsigned numbers but requires the extra end‑around step.

3.3 Two’s‑Complement Subtraction (Preferred)

1. Choose a word length that can hold both operands (including a sign bit).
2. Write the subtrahend in binary.
3. Invert all bits (one’s complement).
4. Add 1 → two’s complement (the negative of the subtrahend).
5. Add this negative to the minuend.
6. If a carry out of the MSB occurs, discard it for signed results (it is ignored for two’s‑complement arithmetic).

Example (5‑bit word): 10101₂ – 00111₂

1. Subtrahend = 00111
2. One’s complement = 11000
3. Two’s complement = 11001 (add 1)
4. Add to minuend:

   1 0 1 0 1
   + 1 1 0 0 1
   -------------
   1 0 0 1 0 0
   

5. Discard the left‑most carry → 01110₂ (decimal 14).

3.4 Signed‑Overflow in Subtraction

Overflow in subtraction can be detected using the same XOR rule as for addition, because subtraction is performed by adding the two’s‑complement of the subtrahend.

Example: 8‑bit 0100 0000₂ (64) – 1100 0000₂ (‑64)

• Two’s‑complement of 1100 0000 = 0100 0000.
• Adding yields 1000 0000 with carry‑in = 0, carry‑out = 1 → XOR = 1 → overflow (result would be 128, which cannot be represented in 8‑bit two’s‑complement).

4. Character Encoding

• ASCII – 7‑bit code (0 – 127). Example: 'A' = 01000001₂.
• Extended ASCII – 8‑bit (0 – 255). Different “code pages” (e.g., Windows‑1252, ISO‑8859‑1) add characters such as € (0x80) or accented letters, but the mapping varies by region.
• Unicode (UTF‑8) – variable‑length (1‑4 bytes) encoding capable of representing over a million characters. The first 128 code points are identical to ASCII, but code points > 127 require more than one byte.
  

  Example: the Euro sign “€” is U+20AC → UTF‑8 bytes 1110 0010 1000 0010 1010 1100 (hex E2 82 AC).

Exercise: Write the 8‑bit ASCII binary code for the character ‘g’ (ASCII 103).

Solution: 103₁₀ = 1100111₂ → padded to 8 bits → 01100111.

5. Practical Applications & Rationale

• Two’s complement is used in virtually all modern CPUs because a single adder circuit can perform both addition and subtraction. The negative of a number is obtained by inverting the bits and adding 1, so subtraction reduces to addition.
• BCD is employed where exact decimal representation is mandatory (e.g., financial calculators, some embedded systems) because each decimal digit is stored separately, avoiding binary‑fraction rounding errors.
• Hexadecimal is the preferred notation for programmers when viewing memory addresses or machine code, as each hex digit maps directly to a 4‑bit nibble.
• Binary prefixes (IEC) are used for memory and storage specifications to avoid the ambiguity of SI prefixes (k, M, G) which are based on powers of 10.
• Floating‑point teaser (A‑Level extension): After mastering integer representations, the next step is the IEEE 754 floating‑point format, which stores numbers in a sign, exponent and mantissa.

6. Practice Questions (Cambridge‑style)

1. Binary addition – Add 1101₂ and 0111₂. Show each column, the carry, and state whether overflow occurs for unsigned 4‑bit addition.
2. Direct borrow subtraction – Subtract 0101₂ from 1010₂. Show the borrowing steps.
3. Two’s‑complement subtraction – Using a 4‑bit word, subtract 0010₂ from 0110₂. Include the formation of the two’s complement, the addition, and the final result.
4. Conversion – Convert the binary number 101101₂ to decimal, hexadecimal and packed BCD.
5. Signed overflow detection – For the signed 8‑bit addition 0110 1101₂ + 0101 0011₂, determine the decimal values, perform the addition, and state whether signed overflow occurs. Explain using the carry‑into‑sign‑bit XOR rule.
6. Character encoding – Write the 8‑bit ASCII binary code for the string “Hi!”. Then give the corresponding hexadecimal representation.
7. Explain (AO2/AO3) – In 150 words, explain why two’s‑complement allows a computer to use a single hardware adder for both addition and subtraction. Include a brief note on overflow handling.
8. Pseudocode (AO2) – Write a short pseudocode routine Subtract_TwosComp(A, B, n) that returns A – B using two’s‑complement arithmetic on n-bit words.

Sample Solution Sketch for Question 5 (Signed Overflow)

Binary values:

• 0110 1101₂ = +109₁₀
• 0101 0011₂ = +83₁₀

Binary addition:

0 1 1 0 1 1 0 1
+ 0 1 0 1 0 0 1 1
-----------------
1 0 0 0 0 0 0 0

Carry into sign bit = 0, carry out = 1 → XOR = 1 → signed overflow. The 8‑bit result 1000 0000₂ represents –128, not the mathematically correct +192.

7. Summary

• Binary addition follows the simple sum‑and‑carry rules; unsigned overflow is indicated by a final carry, signed overflow by CarryintoMSB ⊕ Carryoutof_MSB.
• Binary subtraction can be performed by direct borrowing, but two’s‑complement subtraction (adding the negative) is faster and aligns with hardware design.
• Two’s‑complement is the universal signed representation because it removes the end‑around‑carry step and enables a single adder circuit to handle both addition and subtraction.
• Understanding hexadecimal, BCD, and binary prefixes is essential for interpreting machine code, memory sizes, and decimal‑oriented applications.
• ASCII, extended ASCII and Unicode provide progressively larger character sets; Unicode’s variable‑length encoding solves the limitation of 8‑bit code pages.