What Is Two’s Complement?
For a fixed width of n bits, two’s complement encodes integers in the range −2^(n−1) to +2^(n−1)−1.
- MSB (leftmost bit) is the sign bit (0 = non-negative, 1 = negative).
- Negatives are stored as two’s complement of their absolute value.
- Adding works the same for signed and unsigned; just ignore the extra carry beyond the MSB.
Why it’s great: Only one zero, easy subtraction (add a negative), consistent hardware adders.
How to Make a Negative (Compute Two’s Complement)
Algorithm to get −x from x (n bits)
- Invert all bits of
x(0→1, 1→0). - Add 1 to the inverted result (in n bits).
This is often called “invert + 1”.
Example (8-bit): make −13
+13 = 0000 1101
invert → 1111 0010
+ 1 → 1111 0011 = −13
Example (4-bit): make −5
+5 = 0101
inv → 1010
+1 → 1011 = −5 (4-bit)
How to Read a Negative (Back to Decimal)
Algorithm to decode an n-bit value V
- If MSB is 0, it’s already a non-negative integer.
- If MSB is 1: invert bits, add 1, then put a minus sign in front of the decimal result.
Example (8-bit): 1110 1100
MSB = 1 → negative
invert → 0001 0011
+1 → 0001 0100 = 20
so 1110 1100 = −20
Subtraction Using Two’s Complement (Add a Negative)
Compute A − B in n bits
- Form two’s complement of
B→−B. - Add:
A + (−B)using n-bit addition. - Ignore any carry out of the MSB.
Example (8-bit): 23 − 12
A = 0001 0111 (23)
B = 0000 1100 (12)
−B: invert 1111 0011 ; +1 → 1111 0100
A + (−B):
0001 0111
+ 1111 0100
=1 0000 1011 → keep low 8 bits → 0000 1011 = 11
Example (8-bit): 9 − 13 = −4
A = 0000 1001 (9)
B = 0000 1101 (13)
−B: invert 1111 0010 ; +1 → 1111 0011
A + (−B) = 0000 1001 + 1111 0011 = 1111 1100
Decode: invert 0000 0011 ; +1 → 0000 0100 → −4
Overflow Detection (When the Answer Doesn’t Fit)
Rules (n-bit signed add)
- Overflow occurs iff adding two numbers with the same sign yields a result with a different sign.
- Hardware rule: let
c_inbe carry into MSB andc_outbe carry out; overflow iffc_in XOR c_out = 1.
Positive + Positive → Negative (overflow) (4-bit)
0101 (5)
+0100 (4)
=1001 → sign changed to 1 → overflow
(carry into MSB = 1, carry out = 0 → XOR = 1)
Negative + Negative → Positive (overflow) (4-bit)
1100 (−4)
+1010 (−6)
=0110 → sign changed to 0 → overflow
(carry into MSB = 0, carry out = 1 → XOR = 1)
Adding mixed signs (one positive, one negative) cannot overflow.
n-Bit Signed Ranges & 4-Bit Map
Range formula: with n bits, values are −2^(n−1) … +2^(n−1) − 1.
- 4-bit: −8 … +7
- 8-bit: −128 … +127
- 16-bit: −32768 … +32767
| Binary (4-bit) | Decimal | Binary | Decimal |
|---|---|---|---|
| 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 |
Sign Extension (Changing Bit Width)
Rule
- When widening from n to m bits (
m > n), copy the sign bit into the new upper bits. - This preserves the value.
Example: 4-bit 1011 (−5) → 8-bit
sign bit is 1 → fill with 1s
1011 → 1111 1011 still −5
Example: 4-bit 0110 (+6) → 8-bit
sign bit is 0 → fill with 0s
0110 → 0000 0110 still +6
Truncating bits (reducing width) can change the value; be careful.
Quick Summary
- Make −x: invert bits of x, then add 1 (fixed width).
- Subtract:
A − B = A + (two’s complement of B); drop carry out. - Overflow: same-sign add → different-sign result, or
c_in XOR c_outat MSB. - Ranges:
[−2^(n−1), +2^(n−1)−1]. - Sign-extend when widening.