Chapter 02 of 32

Number Systems & Binary Codes

In Introduction to Digital Electronics we saw that a digital circuit understands only two values, 0 and 1. But we want computers to work with numbers like 156, −45 and 0.6875, and with text like "Hello" and "₹". This chapter answers one question: how do we write all of that using only 0s and 1s?

We will learn the four number systems every engineer uses (decimal, binary, octal, hexadecimal), how to convert between them, how negative numbers are stored (complements), and the most important binary codes: BCD, Excess-3, Gray code and ASCII/Unicode. Every conversion in this chapter was checked with a Python program, shown near the end.


Positional Number Systems

In the decimal number 365, the 3 does not mean "three"; it means "three hundreds" because of its position. Every system we use works the same way, only the base changes.

In a positional number system with base (radix) r, a number uses the digits 0 to r − 1, and the digit in position i has weight ri (positions to the left of the point are 0, 1, 2, ...; to the right they are −1, −2, ...).

(d2 d1 d0 . d-1 d-2)r  =  d2×r² + d1×r¹ + d0×r⁰ + d-1×r⁻¹ + d-2×r⁻²

Example in decimal:  365.25 = 3×100 + 6×10 + 5×1 + 2×0.1 + 5×0.01

System

Base

Digits

Why we use it

Decimal

10

0 to 9

Humans

Binary

2

0, 1

Hardware (two voltage levels)

Octal

8

0 to 7

Short form of binary (3 bits per digit); Unix file permissions like 755

Hexadecimal

16

0 to 9, A (10) to F (15)

Short form of binary (4 bits per digit); memory addresses, colours like #FF8800

We write the base as a subscript to avoid confusion: (101)2 = 5, but (101)10 = one hundred and one. In programming, prefixes are used instead: 0b101, 0o17, 0x1F.

First 16 Numbers in Each Base

Decimal

Binary

Octal

Hex

Decimal

Binary

Octal

Hex

0

0000

0

0

8

1000

10

8

1

0001

1

1

9

1001

11

9

2

0010

2

2

10

1010

12

A

3

0011

3

3

11

1011

13

B

4

0100

4

4

12

1100

14

C

5

0101

5

5

13

1101

15

D

6

0110

6

6

14

1110

16

E

7

0111

7

7

15

1111

17

F


Conversions Between Bases

Any Base → Decimal: Multiply by Weights

(101101.101)₂ = 1×32 + 0×16 + 1×8 + 1×4 + 0×2 + 1×1 + 1×0.5 + 0×0.25 + 1×0.125
              = 32 + 8 + 4 + 1 + 0.5 + 0.125
              = 45.625

(3AF)₁₆ = 3×256 + 10×16 + 15×1 = 768 + 160 + 15 = 943

(734)₈  = 7×64 + 3×8 + 4×1 = 448 + 24 + 4 = 476

Decimal → Any Base: Integer Part by Repeated Division

Divide by the base repeatedly and collect the remainders. The first remainder is the least significant digit, so read them bottom to top.

Convert 156 to binary:

156 ÷ 2 = 78  remainder 0   ← LSB
 78 ÷ 2 = 39  remainder 0
 39 ÷ 2 = 19  remainder 1
 19 ÷ 2 =  9  remainder 1
  9 ÷ 2 =  4  remainder 1
  4 ÷ 2 =  2  remainder 0
  2 ÷ 2 =  1  remainder 0
  1 ÷ 2 =  0  remainder 1   ← MSB

Read upward: 156 = (10011100)₂

Same method for hex:  156 ÷ 16 = 9 remainder 12 (C);  9 ÷ 16 = 0 remainder 9
                      156 = (9C)₁₆

Decimal → Any Base: Fraction Part by Repeated Multiplication

Multiply the fraction by the base; the integer part that pops out is the next digit. Here the first digit is the most significant, so read top to bottom.

Convert 0.6875 to binary:

0.6875 × 2 = 1.375  → 1   ← first digit after the point
0.375  × 2 = 0.75   → 0
0.75   × 2 = 1.5    → 1
0.5    × 2 = 1.0    → 1   (fraction is now 0, stop)

0.6875 = (0.1011)₂      check: 0.5 + 0.125 + 0.0625 = 0.6875 ✓

Convert 0.1 to binary:
0.1→0.2 (0), 0.4 (0), 0.8 (0), 1.6 (1), 1.2 (1), 0.4 (0), 0.8 (0), 1.6 (1), 1.2 (1) ...
0.1 = (0.000110011001100...)₂   ← repeats forever

Why does 0.1 never end? A fraction terminates in base 2 only if its denominator (in lowest terms) is a power of 2. 0.1 = 1/10 and 10 has the factor 5, so it repeats forever. This is why 0.1 + 0.2 is not exactly 0.3 in most programming languages.

Binary ↔ Octal ↔ Hex: Grouping

Because 8 = 23 and 16 = 24, each octal digit is exactly 3 bits and each hex digit exactly 4 bits. Group from the binary point outward, padding with zeros at the ends.

Binary 1011011101 to octal (groups of 3 from the right):
   001 011 011 101
    1   3   3   5     → (1335)₈

Binary 1011011101 to hex (groups of 4 from the right):
   0010 1101 1101
    2    D    D       → (2DD)₁₆

With a fraction: 1101.11 → hex
   1101 . 1100        (pad the fraction on the RIGHT)
    D   .  C          → (D.C)₁₆ = 13.75

Octal to hex: go through binary.  (57)₈ = 101 111 = 0010 1111 = (2F)₁₆

Binary Arithmetic

Binary addition follows the same carry rules as decimal, but you carry at 2 instead of 10.

Rules:  0+0 = 0     0+1 = 1     1+0 = 1     1+1 = 10 (sum 0, carry 1)     1+1+1 = 11

      1 1 1 1        ← carries (into bits 1 to 4)
    1 0 1 1 0 1      (45)
  + 0 0 1 1 1 1      (15)
  ─────────────
    1 1 1 1 0 0      (60) ✓

Subtraction can be done with borrows, but hardware almost never does it that way. Instead it adds the complement, so one adder circuit does both jobs.


Complements

For a base r and an n-digit number N, there are two complements:

(r − 1)'s complement = (rn − 1) − N, i.e. subtract each digit from r − 1.
r's complement = rn − N = (r − 1)'s complement + 1 (and 0 for N = 0).

Base

(r − 1)'s complement

r's complement

10

9's complement of 03250 = 96749

10's complement of 03250 = 96750

2

1's complement of 0101101 = 1010010 (flip every bit)

2's complement of 0101101 = 1010011 (flip, then add 1)

Shortcut for 2's complement: starting from the right, copy all bits up to and including the first 1, then flip every bit to its left. For 0101101: copy the last "1", flip the rest → 1010011.

Subtraction Using r's Complement (M − N)

  1. Add M to the r's complement of N (both n digits).

  2. If there is an end carry, discard it: the result is M − N (positive).

  3. If there is no end carry, the answer is negative: take the r's complement of the sum and put a minus sign.

Example 1: Decimal, 72532 − 3250

M = 72532,  N = 03250,  10's complement of N = 96750

  72532
+ 96750
───────
 169282    → end carry 1, discard it → answer 69282 ✓

Now 3250 − 72532:
10's complement of 72532 = 27468
  03250 + 27468 = 30718   → no end carry, so answer is negative
  10's complement of 30718 = 69282   → answer −69282 ✓

Example 2: Binary, 84 − 67 and 67 − 84 (7 bits)

84 = 1010100,  67 = 1000011

84 − 67 with 2's complement:
  2's complement of 1000011 = 0111101
    1010100
  + 0111101
  ─────────
   10010001   → end carry, discard → 0010001 = 17 ✓

84 − 67 with 1's complement:
  1's complement of 1000011 = 0111100
    1010100 + 0111100 = 1 0010000
  end-around carry: add the carry back to the LSB
    0010000 + 1 = 0010001 = 17 ✓

67 − 84 with 2's complement:
  2's complement of 1010100 = 0101100
    1000011 + 0101100 = 1101111   → no carry, negative
    2's complement of 1101111 = 0010001 → answer −17 ✓

2's complement is preferred in hardware because it needs no end-around carry and has only one representation of zero.


Signed Number Representations

In a register, a negative number has no "−" symbol to use. Three schemes use the leftmost bit (MSB) as the sign (0 = positive, 1 = negative):

Value

Sign-magnitude

1's complement

2's complement

+45

00101101

00101101

00101101

−45

10101101

11010010

11010011

Zero

00000000 and 10000000 (two zeros)

00000000 and 11111111 (two zeros)

00000000 only

8-bit range

−127 to +127

−127 to +127

−128 to +127

n-bit range

−(2n−1 − 1) to 2n−1 − 1

−(2n−1 − 1) to 2n−1 − 1

−2n−1 to 2n−1 − 1

Positive numbers look the same in all three. Every modern computer uses 2's complement for integers (C++20 and C23 even make it mandatory).

A neat way to read a 2's complement number: the MSB has weight −2n−1, all other bits have normal positive weights.

11010011 = −128 + 64 + 16 + 2 + 1 = −45 ✓
11111111 = −128 + 127 = −1

Sign extension: to widen a 2's complement number, copy the sign bit into the new positions. −4 in 4 bits is 1100; in 8 bits it is 11111100.

Overflow

Overflow occurs when the true result of a signed addition is outside the representable range. It happens only when two numbers of the same sign are added and the result has the opposite sign.

8-bit: 100 + 50
  01100100  (+100)
+ 00110010  (+50)
──────────
  10010110  → MSB is 1, reads as −106. True answer 150 > 127: OVERFLOW

Equivalently, overflow = (carry into the MSB) XOR (carry out of the MSB). Adding a positive and a negative number can never overflow. Overflow detection in an adder circuit appears again in Subtractors.


Binary Codes

A binary code is an agreed rule that maps each item of a set (digits, letters, positions) to a unique group of bits. With n bits we can code at most 2n distinct items.

So to code the 10 decimal digits we need at least 4 bits (23 = 8 is too few), and 6 of the 16 patterns go unused.

BCD (8421 Code)

In Binary Coded Decimal, each decimal digit is replaced by its own 4-bit binary value (weights 8, 4, 2, 1). Patterns 1010 to 1111 are invalid.

396 in BCD:   0011 1001 0110      (12 bits, digit by digit)
                3    9    6
396 in binary: 1 1000 1100        (9 bits, whole number)

BCD wastes bits but makes decimal display trivial, so it is used in digital clocks, calculators, 7-segment displays and real-time clock chips. When two BCD digits add to more than 9, a correction of +6 (0110) is needed, because a 4-bit group carries at 16 but a decimal digit must carry at 10 (the 6 unused patterns are skipped). For example, 7 + 5: 0111 + 0101 = 1100 (invalid), + 0110 = 1 0010, i.e. carry 1 and digit 2, giving 12 ✓. Converting between BCD and other codes with gates is covered in Code Converters.

Excess-3 (XS-3)

Each decimal digit d is coded as the binary value of d + 3. 396 → 0110 1100 1001. It is unweighted and self-complementing: flipping all bits of a digit gives the code of its 9's complement (2 = 0101, flip → 1010 = 7, and 9 − 2 = 7). That made decimal subtraction easy in older machines.

2421 Code

A weighted code with weights 2, 4, 2, 1. Using the standard assignment (0 to 4 start with 0, 5 to 9 start with 1), it is also self-complementing.

Digit

BCD 8421

Excess-3

2421

0

0000

0011

0000

1

0001

0100

0001

2

0010

0101

0010

3

0011

0110

0011

4

0100

0111

0100

5

0101

1000

1011

6

0110

1001

1100

7

0111

1010

1101

8

1000

1011

1110

9

1001

1100

1111

Gray Code

In Gray code, consecutive values differ in exactly one bit (a unit-distance code). The last and first values also differ in one bit, so it is cyclic.

Why? Picture a rotating shaft encoder going from 3 to 4. In binary that is 011 → 100: all three bits change. Real contacts never switch at the same instant, so for a moment the reader may see 111 or 000, a huge error. In Gray code, 3 → 4 is 010 → 110: only one bit changes, so the reading is either the old value or the new one, never garbage. Gray code is also the order used to label Karnaugh Maps.

Binary → Gray:  g(MSB) = b(MSB),   g(i) = b(i+1) XOR b(i)     (formula: G = B XOR (B >> 1))

  B = 1 0 1 1
      │╲│╲│╲│
  G = 1 1 1 0          (1, 1⊕0, 0⊕1, 1⊕1)

Gray → Binary:  b(MSB) = g(MSB),   b(i) = b(i+1) XOR g(i)    (XOR with the previous BINARY bit)

  G = 1 1 0 1
  B = 1 → 1⊕1=0 → 0⊕0=0 → 0⊕1=1   →  B = 1001 (= 9)

Decimal

Binary

Gray

Decimal

Binary

Gray

0

0000

0000

8

1000

1100

1

0001

0001

9

1001

1101

2

0010

0011

10

1010

1111

3

0011

0010

11

1011

1110

4

0100

0110

12

1100

1010

5

0101

0111

13

1101

1011

6

0110

0101

14

1110

1001

7

0111

0100

15

1111

1000

Notice the "reflected" pattern: the bottom half (8 to 15) is the top half in reverse order with a 1 in front. That is why it is also called reflected binary code.

Alphanumeric Codes: ASCII and Unicode

ASCII (American Standard Code for Information Interchange) is a 7-bit code with 128 characters: 33 control codes (like newline = 10) and 95 printable characters.

Character

Decimal

Hex

Binary

'0' to '9'

48 to 57

30 to 39

011 0000 to 011 1001

'A' to 'Z'

65 to 90

41 to 5A

100 0001 to 101 1010

'a' to 'z'

97 to 122

61 to 7A

110 0001 to 111 1010

space

32

20

010 0000

Two handy tricks: a digit character minus 48 gives its value ('7' − '0' = 7), and upper and lower case differ by 32, i.e. only in bit 5 ('A' = 100 0001, 'a' = 110 0001).

ASCII cannot write Hindi, Tamil or ₹. Unicode gives every character in every script a code point (U+0000 to U+10FFFF). The most common way to store code points is UTF-8, which uses 1 to 4 bytes per character and keeps plain ASCII text unchanged (1 byte each). For example, ₹ is U+20B9, stored as the 3 bytes E2 82 B9, and अ is U+0905, stored as E0 A4 85.

Error-Detecting Codes (Parity) in One Paragraph

Adding one extra parity bit makes the total number of 1s even (even parity) or odd (odd parity). For 1011001 (four 1s), the even-parity bit is 0 and the odd-parity bit is 1. If any single bit flips during transmission, the count of 1s changes, and the receiver notices. The XOR circuits that generate and check parity are built in Parity Generators & Checkers.


Checking Conversions with a Program

Here is a short Python program that performs the conversions from this chapter using the same algorithms we did by hand (repeated division, repeated multiplication, and XOR for Gray code).

def to_base(n, base):
    """Convert a non-negative integer to a string in the given base (2-16)."""
    digits = "0123456789ABCDEF"
    if n == 0:
        return "0"
    out = ""
    while n > 0:
        out = digits[n % base] + out   # remainder is the next digit (right to left)
        n //= base
    return out

def frac_to_base(f, base, places):
    """Convert a fraction 0 <= f < 1 by repeated multiplication."""
    digits = "0123456789ABCDEF"
    out = ""
    for _ in range(places):
        f *= base
        d = int(f)                     # integer part is the next digit (left to right)
        out += digits[d]
        f -= d
    return out

def gray(n):
    return n ^ (n >> 1)

for n in [156, 45, 943]:
    print(f"{n:4d} -> bin {to_base(n, 2):>12}  oct {to_base(n, 8):>5}  hex {to_base(n, 16):>4}")

print("0.6875 -> binary 0." + frac_to_base(0.6875, 2, 4))
print("0.1    -> binary 0." + frac_to_base(0.1, 2, 12) + "...")
print("int('10011100', 2) =", int("10011100", 2))
print("int('3AF', 16)     =", int("3AF", 16))
print("-45 in 8-bit 2's complement:", format(-45 & 0xFF, "08b"))
print("Gray codes 0-7:", [format(gray(i), "03b") for i in range(8)])

Output:

 156 -> bin     10011100  oct   234  hex   9C
  45 -> bin       101101  oct    55  hex   2D
 943 -> bin   1110101111  oct  1657  hex  3AF
0.6875 -> binary 0.1011
0.1    -> binary 0.000110011001...
int('10011100', 2) = 156
int('3AF', 16)     = 943
-45 in 8-bit 2's complement: 11010011
Gray codes 0-7: ['000', '001', '011', '010', '110', '111', '101', '100']

Common Mistakes

  • Reading division remainders top to bottom. The first remainder is the LSB; read upward. For fractions it is the opposite: the first digit produced is the MSB.

  • Grouping fraction bits from the left end of the number. Always group outward from the binary point, padding the integer part on the left and the fraction on the right.

  • Confusing BCD with binary. 15 in BCD is 0001 0101; in binary it is 1111.

  • Converting Gray to binary by XORing adjacent Gray bits. Each binary bit is the XOR of the previous binary bit and the current Gray bit.

  • Forgetting the sign bit is part of the range. 8-bit 2's complement goes to −128 but only +127.

  • Using the magnitude complement of a negative answer. When there is no end carry in r's complement subtraction, you must complement the result to get the magnitude.

  • Calling ASCII an 8-bit code. Standard ASCII is 7-bit; "extended ASCII" sets are 8-bit and not standard.


GATE and Interview Questions

Q1. If (144)8 = (121)r, find r.

(144)8 = 64 + 32 + 4 = 100. (121)r = r² + 2r + 1 = (r + 1)². So (r + 1)² = 100, r + 1 = 10, r = 9.

Q2. How many 1s are there in the binary form of 4×4096 + 9×256 + 7×16 + 5?

4096 = 163, 256 = 162, so the number is (4975)16 = 0100 1001 0111 0101. Count the 1s: 1 + 2 + 3 + 2 = 8.

Q3. What is the range of a 6-bit 2's complement number? Of 6-bit sign-magnitude?

2's complement: −25 to 25 − 1 = −32 to +31. Sign-magnitude: −31 to +31 (with two zeros).

Q4. Interpret 11100100 as an 8-bit unsigned, sign-magnitude, 1's complement and 2's complement number.

Unsigned: 128 + 64 + 32 + 4 = 228. Sign-magnitude: −(1100100)2 = −100. 1's complement: flip → 00011011 = 27, so −27. 2's complement: −128 + 100 = −28.

Q5. Convert the Gray code 1101 to binary and the binary 1011 to Gray.

Gray 1101 → binary 1001 (= 9). Binary 1011 → Gray 1110.

Q6. Why is 2's complement preferred over 1's complement in computers?

It has a single zero, gives one extra negative value, and subtraction needs no end-around carry, so the same plain adder does both addition and subtraction.

Q7. Which of these codes are self-complementing: 8421 BCD, Excess-3, 2421?

Excess-3 and 2421 (standard assignment). 8421 BCD is not: 3 = 0011 but 6 = 0110, which is not 1100.

Q8. Adding two 8-bit 2's complement numbers gives a carry into the MSB of 1 and a carry out of the MSB of 0. Did overflow occur?

Yes. Overflow = Cin(MSB) ⊕ Cout(MSB) = 1 ⊕ 0 = 1. This is the case of two positive numbers producing a "negative" result.


Summary

  • In base r, digit i has weight ri. Convert to decimal by summing weights; from decimal by repeated division (integer part, read upward) and repeated multiplication (fraction, read downward).

  • Binary ↔ octal ↔ hex: group 3 or 4 bits outward from the point.

  • r's complement = rn − N; (r−1)'s complement = rn − 1 − N. Subtraction becomes addition of the complement.

  • Signed integers: sign-magnitude and 1's complement have two zeros; 2's complement has one zero and range −2n−1 to 2n−1 − 1. Overflow only when same-sign operands give an opposite-sign result.

  • Codes: BCD (digit-wise, 8421), Excess-3 and 2421 (self-complementing), Gray (one bit changes between neighbours), ASCII (7-bit), Unicode/UTF-8 (all scripts, 1 to 4 bytes).

  • Next, in Logic Gates, we meet the circuits that actually process these bits.