Why Number Systems Come First
Every circuit in this course moves bits. Before you can design an adder you must know what the bits mean, how negative numbers are stored, and how the machine detects overflow. This lesson is the foundation for Unit I's arithmetic circuits.
1. Positional Number Systems
| System | Base (r) | Digits | 42 in this base |
|---|---|---|---|
| Binary | 2 | 0, 1 | 101010 |
| Octal | 8 | 0–7 | 52 |
| Decimal | 10 | 0–9 | 42 |
| Hexadecimal | 16 | 0–9, A–F | 2A |
The value of a number in base r is the weighted sum of its digits:
N = dn·r^n + ... + d1·r^1 + d0·r^0 + d-1·r^-1 + ...
Check: 101010(2) = 32 + 8 + 2 = 42 ✓
52(8) = 5x8 + 2 = 42 ✓
2A(16) = 2x16 + 10 = 42 ✓2. Conversions — the four cases
(a) Any base → decimal: multiply by positional weights
1101.101(2)
= 1x8 + 1x4 + 0x2 + 1x1 + 1x0.5 + 0x0.25 + 1x0.125
= 13.625(10)(b) Decimal → any base: divide the integer part, multiply the fraction
Integer part 45 -> binary Fraction 0.6875 -> binary
45 / 2 = 22 rem 1 (LSB) 0.6875 x 2 = 1.375 -> 1 (MSB)
22 / 2 = 11 rem 0 0.375 x 2 = 0.75 -> 0
11 / 2 = 5 rem 1 0.75 x 2 = 1.5 -> 1
5 / 2 = 2 rem 1 0.5 x 2 = 1.0 -> 1 (stop)
2 / 2 = 1 rem 0
1 / 2 = 0 rem 1 (MSB)
Read remainders bottom-to-top: 101101
Read products top-to-bottom: .1011
45.6875(10) = 101101.1011(2)(c) Binary ↔ octal: group in 3 bits from the binary point
101 101 . 101 100
5 5 5 4 -> 55.54(8)(d) Binary ↔ hexadecimal: group in 4 bits from the binary point
0010 1101 . 1011
2 D B -> 2D.B(16)Exam tip: never convert octal→hex directly. Always route through binary: octal → binary → regroup → hex.
3. Complements — how the machine subtracts
A computer has no subtractor; it has an adder and a complementer. Two complements exist for base r:
| Complement | Formula | Binary name |
|---|---|---|
| (r−1)'s complement | (r^n − 1) − N | 1's complement — flip every bit |
| r's complement | r^n − N | 2's complement — flip every bit, add 1 |
N = 0101100 (44)
1's comp = 1010011 (flip each bit)
2's comp = 1010100 (flip, then +1)
Shortcut for 2's complement: scan from the LSB, copy bits up to and
including the FIRST 1, then flip everything to the left.
0101100
^ first 1 from right (copy '100'), flip the rest '0101' -> '1010'
= 1010100 ✓Subtraction by 2's complement
Compute 45 - 27 using 8-bit 2's complement.
45 = 0010 1101
27 = 0001 1011
-27 = 1110 0101 (2's complement of 27)
0010 1101
+ 1110 0101
------------
1 0001 0010 <- carry out of the MSB
^ DISCARD this end carry
Result 0001 0010 = 18 ✓ (45 - 27 = 18)Rule: in 2's complement, an end carry is simply discarded and the answer is positive. If there is no end carry, the answer is negative and is itself in 2's complement form — take its 2's complement to read the magnitude.
4. Signed Number Representations
For 4 bits (MSB = sign bit, 0 = positive, 1 = negative):
| Decimal | Signed magnitude | 1's complement | 2's complement |
|---|---|---|---|
| +7 | 0111 | 0111 | 0111 |
| +1 | 0001 | 0001 | 0001 |
| +0 | 0000 | 0000 | 0000 |
| −0 | 1000 | 1111 | (does not exist) |
| −1 | 1001 | 1110 | 1111 |
| −7 | 1111 | 1000 | 1001 |
| −8 | — | — | 1000 |
Why 2's complement wins: single representation of zero, range is one value larger (−8…+7 instead of −7…+7), and ordinary binary addition works for signed numbers with no special-case hardware.
Range for n bits:
Signed magnitude / 1's complement: -(2^(n-1) - 1) to +(2^(n-1) - 1)
2's complement: -2^(n-1) to +(2^(n-1) - 1)5. Overflow Detection
Overflow means the true result does not fit in n bits. It can occur only when both operands have the same sign.
8-bit signed addition:
0100 0000 (+64) 1100 0000 (-64)
+ 0100 0000 (+64) + 1100 0000 (-64)
----------- -----------
1000 0000 (-128!) 1 1000 0000 (-128 after discarding carry, but true answer -128 fits... )
Detection rule: Overflow = C(n) XOR C(n-1)
i.e. carry INTO the sign bit differs from carry OUT of the sign bit.6. Binary Codes
| Code | Idea | 9 in this code | Where used |
|---|---|---|---|
| BCD (8421) | Each decimal digit in 4 bits | 1001 | Calculators, digital displays |
| Excess-3 | BCD + 0011 | 1100 | Self-complementing arithmetic |
| Gray code | Only one bit changes between neighbours | 1101 | Shaft encoders, K-map ordering |
| ASCII | 7-bit character code | '9' = 0111001 | Text representation |
Binary ↔ Gray conversion
Binary -> Gray: G(MSB) = B(MSB); G(i) = B(i+1) XOR B(i)
B = 1 0 1 1
G = 1 (1^0) (0^1) (1^1) = 1 1 1 0
Gray -> Binary: B(MSB) = G(MSB); B(i) = B(i+1) XOR G(i)
G = 1 1 1 0
B = 1 (1^1) (0^1) (1^0) = 1 0 1 1 ✓Why Gray code matters in this course: K-map rows and columns are labelled in Gray-code order (00, 01, 11, 10) precisely so that adjacent cells differ in exactly one variable — that adjacency is what makes simplification possible.
Quick Revision Table
| Concept | One-line summary |
|---|---|
| Base-r value | Weighted sum of digits with weights r^i |
| Decimal → base r | Divide integer, multiply fraction |
| 1's complement | Flip all bits |
| 2's complement | Flip all bits + 1 (or copy up to first 1 from right, flip rest) |
| Subtraction | Add the 2's complement, discard the end carry |
| Overflow | Carry-in to sign bit ≠ carry-out of sign bit |
| Gray code | Exactly one bit changes between consecutive values |
With numbers understood, the next lesson introduces the algebra that describes the circuits which manipulate them.