Signed integers: 2's complement, ranges, sign extension, overflow; bit fields and shifts

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• How many address bits for a 256 MB byte-addressable memory? from Lesson 0.2.1
• What is CPI? from Lesson 0.1.2
• What does the data bus carry, and in which direction? from Lesson 0.1.1

1 · The Hook

🎣

An ALU adds bit patterns. It has no idea whether 1111 1111 means 255 or −1. The trick that lets the same adder handle positive and negative numbers is two's complement. You need it for the ALU (Phase 2), for branch offsets that jump backwards (Phase 1), and for every overflow question.

2 · Predict First

🤔

In 8 bits, 0111 1111 is 127. Add 1. The adder produces 1000 0000. If the bits are read as a signed number, what value is that? What went wrong?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

1000 0000 is −128 in 8-bit two's complement. Adding two positive numbers gave a negative result: the true answer 128 does not fit in 8 signed bits. That is overflow.

Unsigned numbers

n bits read as an unsigned number cover 0 to 2ⁿ − 1. 8 bits: 0 … 255.

Two's complement

The leftmost bit (MSB) has weight −2ⁿ⁻¹ instead of +2ⁿ⁻¹; the other bits keep their usual weights.

• 8-bit 1110 1100 = −128 + 64 + 32 + 8 + 4 = −20.
• Range: −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1. 8 bits: −128 … 127. 16 bits: −32,768 … 32,767.
• MSB = 1 means negative.
• To negate: invert every bit, then add 1. 20 = 0001 0100 → invert 1110 1011 → +1 → 1110 1100 = −20.

The same adder adds two's-complement numbers correctly: just add the bits and drop any carry out of the MSB.

Sign extension

To widen an n-bit signed number, copy the sign bit into the new positions: −20 = 1110 1100 → 16 bits 1111 1111 1110 1100 = 0xFFEC. Positive numbers get zeros. (Unsigned numbers are widened with zeros: zero extension.)

Overflow

Signed overflow happens when the true result lies outside the range. Test: adding two numbers of the same sign gives a result of the other sign. Adding numbers of opposite signs never overflows. The carry out of the MSB is a different thing: it signals unsigned overflow, not signed overflow.

Shifts

• Logical left shift by k: move bits left, fill zeros on the right → multiplies by 2ᵏ (if nothing important falls off).
• Logical right shift: fill zeros on the left → unsigned division by 2ᵏ.
• Arithmetic right shift: fill with copies of the sign bit → signed division by 2ᵏ, rounding toward −∞. 1110 1100 (−20) >> 2 arithmetic = 1111 1011 = −5.

Bit fields

Instructions and addresses are bit fields packed into one word. To read bits from position j up to position i (bit 0 is the rightmost): shift right by j, then keep the low (i − j + 1) bits with a mask (AND with 2^(i−j+1) − 1).

Example: 16-bit word 0xA7C3 = 1010 0111 1100 0011. Bits 15–12 = 1010 = 10; bits 11–8 = 0111 = 7; bits 7–0 = 0xC3.

4 · Visual

Weights of an 8-bit two's-complement number
 bit:      7     6    5    4   3   2   1   0
 weight: -128   64   32   16   8   4   2   1

5 · Worked Examples

Example 1 Easy

Write −37 in 8-bit two's complement.

Solution

37 = 0010 0101 → invert 1101 1010 → +1 → 1101 1011.

Example 2 Medium

Add 8-bit signed 0110 0100 (100) and 0011 0010 (50). Result bits? Overflow?

Solution

1001 0110. Both operands positive, result MSB is 1 → overflow. Read as signed, 1001 0110 = −106; the true sum 150 exceeds 127.

Example 3 GATE

A 16-bit word holds 0x8A3F. What value do bits 11 to 6 hold (as an unsigned number)?

Solution

0x8A3F = 1000 1010 0011 1111. Bits 11–6: shift right by 6 → 10 0010 1000 (0x228); keep low 6 bits: 10 1000 = 40.

6 · GATE Traps

⚠️

• Range is asymmetric: −128 … 127 in 8 bits; −(−128) does not fit.
• Overflow (signed) ≠ carry out (unsigned).
• Sign extension copies the sign bit; zero extension is for unsigned values.
• Arithmetic right shift of −5 by 1 gives −3 (rounds toward −∞), not −2.

7 · Memory Hook

🧠

"Flip and add one" to negate. "Same signs in, other sign out = overflow."

8 · Connect the Dots

You now read any bit pattern as unsigned or signed and can slice fields out of a word. Next: the hardware pieces (gates, multiplexers, decoders, adders, registers, buses) that all of Phases 2 and 3 are built from.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markRange

What is the most negative value of a 12-bit two's-complement number?

Numerical answer: ________

Q2MCQ1 markTwo's complement value

The 8-bit two's-complement pattern 1111 0110 represents:

• (A) −10
• (B) −9
• (C) 246
• (D) −118

Q3MSQ2 marksOverflow

Which 8-bit signed additions overflow?

• (A) 120 + 10
• (B) −100 + (−30)
• (C) 100 + (−120)
• (D) 64 + 63

Q4MCQ1 markSign extension

The 8-bit signed value 1010 0001 is sign-extended to 16 bits. The result in hex is:

• (A) 0xFFA1
• (B) 0xA100
• (C) 0x00A1
• (D) 0x80A1

Q5NAT2 marksBit field

A 16-bit word is 0xC5B2. What unsigned value do bits 9 to 4 hold?

Numerical answer: ________

10 · Rule Card

• Unsigned: 0 … 2ⁿ−1. Two's complement: −2ⁿ⁻¹ … 2ⁿ⁻¹−1; MSB weight −2ⁿ⁻¹.
• Negate: invert and add 1. Sign-extend by copying the MSB.
• Signed overflow: same-sign operands, other-sign result. Carry out = unsigned overflow.
• Left shift ×2ᵏ; logical right shift for unsigned; arithmetic right shift keeps the sign.
• Field bits i..j: (word >> j) AND (2^(i−j+1) − 1).

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

unsigned rangetwo's complementnegation (invert + 1)sign extensionzero extensionsigned overflowcarry outlogical shiftarithmetic shiftbit field and mask

12 · Answer Vault