1. ALU Structure and Operations

The Arithmetic Logic Unit (ALU) is the computational core of the CPU. It takes two operands from registers (or one operand for shifts/NOT), performs an operation selected by the control unit, and produces a result plus condition flags.

The condition flags register (also called the status register or flags register) captures properties of the last ALU result:

• Z (Zero): result is zero
• N (Negative/Sign): MSB of result is 1 (result is negative in two’s complement)
• C (Carry): carry out of MSB for unsigned arithmetic
• V (Overflow): signed arithmetic overflow — result does not fit in the register

2. Integer Number Representation

Two’s complement is universally used in modern CPUs because: (1) unique zero, (2) addition and subtraction use the same hardware, and (3) overflow detection is simple.

3. Two’s Complement — Addition & Subtraction

Example: 8-bit two’s complement

4. Overflow Detection

5. Adder Types — Ripple Carry vs Carry Lookahead

Ripple Carry Adder (RCA)

Chain n full adders, each taking the carry out of the previous stage as carry in. Simple, small, but slow — carry must propagate through all n stages.

Carry Lookahead Adder (CLA)

Compute all carries simultaneously using generate (G) and propagate (P) signals, avoiding the ripple delay.

6. Binary Multiplication & Booth’s Algorithm

Basic Binary Multiplication

Binary multiplication uses the same principle as long multiplication: generate partial products (each bit of the multiplier either selects the multiplicand shifted left, or zero), then sum all partial products.

Booth’s Algorithm

Booth’s algorithm reduces the number of add/subtract operations needed for multiplication, especially when the multiplier has long runs of 1s. It correctly handles signed (two’s complement) multiplication without special cases.

The key insight: a run of k consecutive 1s in the multiplier (e.g., 011110) can be replaced by (100000 − 000010), i.e., one addition and one subtraction rather than k additions.

Booth’s Algorithm Procedure (for n-bit numbers):

1. Initialise: Accumulator A = 0, Q = multiplier, Q_{−1} = 0
2. Repeat n times:
   • Check Q_0 (LSB of Q) and Q_{−1}
   • If 01: A = A + multiplicand (M)
   • If 10: A = A − multiplicand (A + two’s complement of M)
   • If 00 or 11: no operation
   • Arithmetic right shift {A, Q, Q_{−1}} by 1 (shift MSB of Q into LSB of A, shift LSB of Q into Q_{−1})
3. Result = {A, Q} (2n bits)

7. IEEE 754 Floating-Point Representation

Integer arithmetic is exact but limited in range. Floating-point represents a vast range of values by separating a number into a sign, an exponent (scaling factor), and a mantissa (significant digits).

Special Values in IEEE 754

Steps to convert decimal to IEEE 754 single precision:

1. Determine sign bit S (0 for positive, 1 for negative)
2. Convert magnitude to binary
3. Normalise: move binary point to get 1.xxx × 2^n
4. Exponent stored = n + 127 (add bias)
5. Mantissa = xxx… (the fractional part, padded to 23 bits)

8. GATE-Level Worked Examples

Example 1 — Two’s Complement Subtraction (GATE 2020)

Problem: Using 8-bit two’s complement, compute 45 − 73. State whether overflow occurs.

Example 2 — Booth’s Algorithm (GATE 2022 style)

Problem: Use Booth’s algorithm to multiply +6 × (−3) using 4-bit representation.

Example 3 — IEEE 754 Encoding (GATE 2021)

Problem: Represent −10.75 in IEEE 754 single precision.

9. Common Mistakes

1. Applying two’s complement range incorrectly
   For n bits, the range is −2^(n−1) to +2^(n−1) − 1 (asymmetric). The most negative number (−128 for 8 bits) has no positive counterpart in 8 bits — negating it causes overflow. Students often forget this asymmetry and write −127 to +127.
2. Confusing signed overflow (V flag) with carry (C flag)
   Carry out of the MSB signals unsigned overflow — the result does not fit as an unsigned number. The overflow flag (V) signals signed overflow. They are independent — it is perfectly valid to have carry without overflow (two large unsigned numbers whose signed interpretation is fine) and overflow without carry.
3. Forgetting the implicit leading 1 in IEEE 754 normal numbers
   Normal floating-point numbers are represented as 1.M × 2^(E−bias). The leading 1 is not stored — it is implied. The mantissa bits only represent the fractional part. Forgetting this makes the precision seem 23 bits when it is actually 24 bits (23 stored + 1 implicit).
4. Using the wrong bias in IEEE 754 exponent calculations
   Single precision bias = 127 (not 128). Double precision bias = 1023. The stored exponent = actual exponent + bias. Students sometimes confuse the formula direction — stored exponent = actual + bias, so actual = stored − bias.
5. Arithmetic vs logical right shift
   Logical right shift fills the MSB with 0. Arithmetic right shift fills the MSB with the sign bit (extends the sign). Booth’s algorithm and two’s complement division require arithmetic right shift. Using logical shift gives the wrong result for negative numbers.

10. Frequently Asked Questions

How do you perform two’s complement subtraction?

To compute A − B: find the two’s complement of B (invert all bits and add 1), then add A + (two’s complement of B) using the regular binary adder. The carry out of the MSB is discarded for the result but is used for overflow detection. This is exactly how CPUs perform subtraction — a single adder handles both addition and subtraction by feeding in the two’s complement of the subtrahend.

What is Booth’s algorithm?

Booth’s algorithm is a signed binary multiplication technique that works directly with two’s complement numbers. It examines consecutive bit pairs of the multiplier and decides: add the multiplicand (at a 0→1 transition), subtract the multiplicand (at a 1→0 transition), or do nothing (same consecutive bits). Each step is followed by an arithmetic right shift. After n steps (for n-bit numbers), the product is in the combined accumulator+multiplier register.

What is the IEEE 754 floating-point format?

IEEE 754 is the standard for floating-point arithmetic. A 32-bit single-precision number has 1 sign bit, 8 exponent bits (stored with bias 127), and 23 mantissa bits (with an implicit leading 1). The value is (−1)^S × 1.M × 2^(E−127). Special encodings represent zero, infinity, and NaN (Not a Number). Double precision uses 64 bits: 1 sign + 11 exponent (bias 1023) + 52 mantissa.

What is the difference between ripple carry adder and carry lookahead adder?

A ripple carry adder chains n full adders — each carry must arrive at the next stage before it can compute its output, so total delay scales linearly with n bits. A carry lookahead adder computes all carry bits simultaneously using generate (G = A AND B) and propagate (P = A XOR B) signals — each carry can be computed in O(1) gates without waiting for previous stages. This gives O(log n) delay at the cost of more hardware.