Two's complement signed numbers: Exercises — Hardware deep dive

A tiny reminder of the two facts we lean on constantly:

Level 1 — Recognition

(Just read the bits. No arithmetic tricks yet.)

L1.1 Is the 8-bit pattern 10011010 positive or negative? What is the weight of its most significant bit?

Recall Solution — L1.1

The most significant bit (leftmost, $b_{7}$ ) is 1. In two's complement a 1 in the top position means the number is negative. Its weight is not $+ 128$ but $- 2^{7} = - 128$ . Answer: negative; MSB weight $= - 128$ .

L1.2 For a 6-bit two's complement number, write down the exact representable range.

Recall Solution — L1.2

Range for $n$ bits is $[- 2^{n - 1}, 2^{n - 1} - 1]$ . Here $n = 6$ , so $2^{n - 1} = 2^{5} = 32$ . Answer: $[- 32, + 31]$ .

L1.3 Which of these 8-bit patterns represent negative numbers? 00000000, 01111111, 10000000, 11111111.

Recall Solution — L1.3

Look only at the top bit.

00000000 → top bit 0 → non-negative (it is $0$ ).
01111111 → top bit 0 → non-negative ( $+ 127$ ).
10000000 → top bit 1 → negative ( $- 128$ ).
11111111 → top bit 1 → negative ( $- 1$ ). Answer: the last two are negative.

Level 2 — Application

(Turn the crank: encode, decode, negate.)

L2.1 Encode $- 19$ in 8-bit two's complement.

Recall Solution — L2.1

Write $+ 19$ : $16 + 2 + 1 \Rightarrow$ 00010011. Why: start from the known positive.
Flip every bit: 11101100. Why: $\overset{x}{ˉ} = 2^{n} - 1 - x$ .
Add 1: 11101101. Why: $\overset{x}{ˉ} + 1 = 2^{n} - x \equiv - x$ . Check by weights: $- 128 + 64 + 32 + 8 + 4 + 1 = - 128 + 109 = - 19$ . ✓ Answer: 11101101.

L2.2 Decode the 8-bit pattern 11001101.

Recall Solution — L2.2

Top bit is 1 → negative, weight $- 128$ . Add the positive weights of the remaining 1s: positions set below the top are $6, 3, 2, 0$ → $64 + 8 + 4 + 1 = 77$ . $V = - 128 + 77 = - 51$ . Shortcut check: negate (flip+1): 11001101 → flip 00110010 → +1 00110011 $= 51$ . So original $= - 51$ . ✓ Answer: $- 51$ .

L2.3 Compute $12 - 20$ in 8-bit two's complement by adding the negative.

Recall Solution — L2.3

$12 =$ 00001100. Encode $- 20$ : $+ 20 =$ 00010100 → flip 11101011 → +1 11101100. Add: $00001100 + 11101100 = 11111000$ No carry drops off the top here. Decode 11111000: $- 128 + 64 + 32 + 16 + 8 = - 128 + 120 = - 8$ . Answer: $- 8$ (as expected, $12 - 20 = - 8$ ). ✓

Level 3 — Analysis

(Now explain why things behave — especially the edge cases.)

L3.1 Negate $- 128$ in 8-bit two's complement (10000000). What do you get, and why?

Recall Solution — L3.1

Flip 10000000 → 01111111; add 1 → 10000000. We are back where we started. Why: $- 128$ has no positive twin. Its true negation would be $+ 128$ , but $+ 128 > 127$ is outside the range $[- 128, + 127]$ , so it wraps. Formally $- (- 128) = 128 \equiv 128 - 256 = - 128 (mod 256)$ . Answer: 10000000 $= - 128$ — negation overflows to itself.

L3.2 Add $100 + 45$ in 8-bit signed. Is the unsigned carry-out set? Is there signed overflow? Are those the same thing?

Recall Solution — L3.2

$100 =$ 01100100, $45 =$ 00101101. $01100100 + 00101101 = 10010001$ Carry-out (9th bit): none — the sum fits in 8 bits, so $C_{n} = 0$ . Signed value of 10010001: $- 128 + 16 + 1 = - 111$ . Two positives gave a negative → signed overflow ( $100 + 45 = 145 > 127$ ). Check the flag rule: carry into MSB $C_{n - 1} = 1$ (needed to make the top bit flip), carry out $C_{n} = 0$ , so $C_{n - 1} \oplus C_{n} = 1 \Rightarrow$ overflow. ✓ Answer: carry-out $= 0$ , but signed overflow $= 1$ . They are different flags — see Overflow and carry flags.

L3.3 Show that in 8-bit, the patterns 01111111 and 10000000 are the two range endpoints, and that adding 1 to each is the "danger" moment.

Recall Solution — L3.3

01111111 $= 0 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 127 = 2^{7} - 1$ → the largest positive. 10000000 $= - 128 = - 2^{7}$ → the most negative. Add 1 to 01111111: → 10000000 = $- 128$ . Two positives ( $127 + 1$ ) wrapping to negative → overflow. Add 1 to 11111111 ( $= - 1$ ): → 00000000 = $0$ — that one is fine ( $- 1 + 1 = 0$ , in range). Answer: endpoints are $- 128$ and $+ 127$ ; incrementing $+ 127$ overflows, incrementing $- 1$ does not.

Level 4 — Synthesis

(Combine several ideas into one problem.)

L4.1 A CPU computes 11110110 + 00011001 in 8-bit signed. Give: (a) the raw 9-bit sum, (b) whether the carry-out is discarded, (c) the final signed value, (d) whether there is overflow.

Recall Solution — L4.1

Decode inputs first: 11110110 $= - 128 + 64 + 32 + 16 + 4 + 2 = - 10$ ; 00011001 $= 16 + 8 + 1 = 25$ . Add the bytes: $11110110 + 00011001 = 100001111$ (a) Raw 9-bit result 1 00001111. (b) Carry-out $C_{8} = 1$ — discarded, because it is worth $2^{8} = 256 \equiv 0 (mod 256)$ . (c) Remaining 8 bits 00001111 $= 8 + 4 + 2 + 1 = 15$ . And indeed $- 10 + 25 = 15$ . ✓ (d) Overflow? Operands have opposite signs ( $- 10$ and $+ 25$ ), so overflow is impossible — a negative plus a positive always lands inside the range. Check flags: carry into MSB $C_{7} = 1$ , carry out $C_{8} = 1$ , $1 \oplus 1 = 0$ → no overflow. ✓ Answer: (a) 1 00001111, (b) yes discarded, (c) $+ 15$ , (d) no overflow.

L4.2 Using 4-bit two's complement, list every pattern and its value, then confirm the "one more negative than positive" claim.

Recall Solution — L4.2

Top bit $b_{3}$ has weight $- 8$ ; the rest are $+ 4, + 2, + 1$ .

bits	value	bits	value
0000	0	1000	−8
0001	1	1001	−7
0010	2	1010	−6
0011	3	1011	−5
0100	4	1100	−4
0101	5	1101	−3
0110	6	1110	−2
0111	7	1111	−1

Negatives: $- 8$ through $- 1$ = 8 values. Positives: $+ 1$ through $+ 7$ = 7 values. Plus one zero. Total $16 = 2^{4}$ . ✓ Answer: range $[- 8, + 7]$ ; exactly one more negative ( $- 8$ ) than positive, because the single zero code frees one extra pattern for the negatives.

Level 5 — Mastery

(Prove and generalise.)

L5.1 Prove the negation rule $- x = \overset{x}{ˉ} + 1 (mod 2^{n})$ from the single fact $x + \overset{x}{ˉ} = 2^{n} - 1$ . Then explain in one line why it fails to give a valid same-width result for exactly one input.

Recall Solution — L5.1

Proof. For any $n$ -bit $x$ , each bit position contributes a 1 to either $x$ or $\overset{x}{ˉ}$ but never both, so bit-by-bit $x + \overset{x}{ˉ}$ is all ones: $x + \overset{x}{ˉ} = n 11 \dots 1 = 2^{n} - 1.$ Rearrange: $\overset{x}{ˉ} = 2^{n} - 1 - x$ , hence $\overset{x}{ˉ} + 1 = 2^{n} - x .$ > Working mod $2^n$, $2^{n} \equiv 0$ , so $2^{n} - x \equiv - x (mod 2^{n})$ . Therefore $\overset{x}{ˉ} + 1 \equiv - x$ . $■$ The failing input: $x = - 2^{n - 1}$ (e.g. $- 128$ for $n = 8$ ). Then $- x = + 2^{n - 1}$ , which is out of range $[- 2^{n - 1}, 2^{n - 1} - 1]$ ; the formula wraps it back to $- 2^{n - 1}$ itself. Every other value has a valid negation.

L5.2 Design a subtraction: show that computing $A - B$ as $A + \overset{ˉ}{B} + 1$ needs no separate subtractor — only the Full adder chain plus one control bit. Demonstrate on $5 - 8$ in 8-bit.

Recall Solution — L5.2

Construction. From L5.1, $- B \equiv \overset{ˉ}{B} + 1 (mod 2^{n})$ . So $A - B = A + (- B) = A + \overset{ˉ}{B} + 1 (mod 2^{n}) .$ Feed $\overset{ˉ}{B}$ into the adder and set the very first carry-in $C_{0} = 1$ (that supplies the " $+ 1$ " for free). A SUB control line can both invert $B$ and set $C_{0} = 1$ ; when it is 0, $B$ passes straight through and $C_{0} = 0$ , giving plain addition. One adder, two modes. Demonstration $5 - 8$ : $A = 5 =$ 00000101, $B = 8 =$ 00001000, $\overset{ˉ}{B} =$ 11110111, $C_{0} = 1$ . $00000101 + 11110111 + 1 = 111111101$ Drop the carry-out ( $2^{8}$ , invisible). Result 11111101. Decode: $- 128 + 64 + 32 + 16 + 8 + 4 + 1 = - 3$ . And $5 - 8 = - 3$ . ✓ Answer: the identity $A - B = A + \overset{ˉ}{B} + 1$ turns subtraction into "invert $B$ , carry-in 1," so the same adder does both; $5 - 8 = - 3$ .

L5.3 Prove the overflow rule " $C_{n - 1} \oplus C_{n}$ " for the same-sign case by a counting argument: why must two positives that overflow produce a 1 in the top bit?

Recall Solution — L5.3

Take two positives $a, b \in [0, 2^{n - 1} - 1]$ , so both have top bit 0. Their true sum $s = a + b$ lies in $[0, 2^{n} - 2]$ .

No overflow case: $s \leq 2^{n - 1} - 1$ . Then $s$ still fits with top bit 0. No carry crosses into the MSB from the lower bits large enough to flip it, so $C_{n - 1} = 0$ ; and no carry leaves the top, $C_{n} = 0$ . XOR $= 0$ . ✓
Overflow case: $s \geq 2^{n - 1}$ . To reach a sum $\geq 2^{n - 1}$ from two numbers whose top bits are 0, the lower $n - 1$ bits must produce a carry into the MSB: $C_{n - 1} = 1$ . That carry sets the top bit to 1 (a negative-looking result), while nothing carries out since $s < 2^{n}$ : $C_{n} = 0$ . XOR $= 1 \oplus 0 = 1$ . ✓ By symmetry, two negatives overflow with $C_{n - 1} = 0, C_{n} = 1$ , again XOR $= 1$ . Opposite-sign operands can never push $s$ outside the range, so they never trigger it. Conclusion: overflow $⟺ C_{n - 1} \oplus C_{n} = 1$ . $■$

Connections

Binary number system — the unsigned weights every problem starts from
One's complement — the "flip only" step, why it is one short
Modular arithmetic — why dropping the carry-out is exact
Full adder — the circuit L5.2 reuses for subtraction
Overflow and carry flags — the two different flags L3 and L4 separate