SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 2

CS Fundamentals for Placements · Lesson 2 of 90 · 15 min

Number systems: binary, octal, decimal, hexadecimal

positional notationradix/basebinaryoctaldecimalhexadecimalbase conversion (repeated division, weighted sum)grouping shortcut binary to octal/hexfractional conversion (repeated multiplication)MSBLSBBCDexcess-3 codeGray code

These are the notes for CS Fundamentals for Placements, episode 2. Last episode, we saw that a computer stores everything as bits. Here you learn to count and convert like a computer, by hand and in code. You will invent each idea yourself, one problem at a time: positional notation and the base, reading binary with the weighted sum, converting from decimal by repeated division (after our first converter breaks), the grouping shortcut for octal and hexadecimal, fractions by repeated multiplication, MSB, LSB and how many bits a number needs, and three special codes: BCD, excess-3 and Gray code. Every Python demo below is self-contained and runs as-is; the outputs shown are real (Python 3.13). Every term is defined in the Glossary near the end.

The six problems

Problem What it teaches
Counting with tally marks Positional notation, place value, base (radix)
Read 101101 Binary, the weighted sum
Our converter breaks on 6 Repeated division, read the remainders bottom to top
Bits too long to read Octal (groups of 3) and hexadecimal (groups of 4)
What about 0.625? Fractions in binary: repeated multiplication
A dial reads garbage BCD, excess-3, Gray code

Problem 1: the milkman's wall (place value)

A milkman delivers milk every day, and his customer draws one line on the wall for each litre: |||| ||. Easy at first. By the end of the month there are 240 lines. Count them and you will lose your place. One symbol per unit does not scale.

So we write 240 instead. Three symbols say it all. The idea that makes this work: where a digit sits changes what it is worth. The 2 in 240 is not "two", it is "two hundreds".

Positional notation

A digit's value = the digit × its place value.

472 = 4×100 + 7×10 + 2×1
    = 4×10² + 7×10¹ + 2×10⁰

Each place is ten times the place on its right. Why ten? Because we have ten digits, 0 to 9. The number of digits a system uses is its base, also called its radix. Decimal is base 10.

Nothing forces ten. In base b you have b digits (0 to b−1), and the places are b⁰, b¹, b², b³, and so on, from the right.

Base = how many digits exist. Base b uses digits 0 to b−1, never b itself.

Problem 2: reading binary (the weighted sum)

A bit has only two states, so a computer counts in base 2, called binary. Only two digits: 0 and 1. In base 2 each place is double the one on its right.

Place value 32 16 8 4 2 1
Power of 2 2⁵ 2⁴ 2³ 2² 2¹ 2⁰
Bits of 101101 1 0 1 1 0 1
Bit × place 32 0 8 4 0 1

A 0 adds nothing, so just add the places that hold a 1: 32 + 8 + 4 + 1 = 45. This is the weighted sum, and it works for any base: digit × place value, added up.

Other bases, same method:

octal 17   = 1×8 + 7×1           = 15
hex 2D7    = 2×256 + 13×16 + 7×1 = 512 + 208 + 7 = 727
binary 1101.101 = 8 + 4 + 0 + 1 + 1/2 + 0/4 + 1/8 = 13.625

Demo 1: the weighted sum in code

# binary → decimal: the weighted sum
bits = "101101"

total = 0
for i, b in enumerate(reversed(bits)):   # i = place, from the right
    total = total + int(b) * 2**i
    print(f"bit {b} x 2^{i} = {int(b) * 2**i}")

print("decimal:", total)
print("check:  ", int(bits, 2))

Output:

bit 1 x 2^0 = 1
bit 0 x 2^1 = 0
bit 1 x 2^2 = 4
bit 1 x 2^3 = 8
bit 0 x 2^4 = 0
bit 1 x 2^5 = 32
decimal: 45
check:   45

reversed(bits) walks from the right, so i is the place number 0, 1, 2 … int(bits, 2) is Python's own converter: it reads a string in base 2.

Problem 3: decimal to binary (repeated division)

To go the other way, divide by 2 and write down the remainder. The first remainder is the ones place, because it is what is left after taking out all the twos. Keep dividing the answer until it reaches 0.

Step Divide Quotient Remainder
1 45 ÷ 2 22 1 ← LSB (rightmost bit)
2 22 ÷ 2 11 0
3 11 ÷ 2 5 1
4 5 ÷ 2 2 1
5 2 ÷ 2 1 0
6 1 ÷ 2 0 1 ← MSB (leftmost bit)

Read the remainders bottom to top: 101101. This is repeated division.

Demo 2: the obvious code (and its bug)

# decimal → binary: keep dividing by 2
def to_binary(n):
    digits = ""
    while n > 0:
        digits = digits + str(n % 2)   # the remainder
        n = n // 2
    return digits

print("45 ->", to_binary(45))
print("6  ->", to_binary(6))
print("check:", bin(45), bin(6))

Output:

45 -> 101101
6  -> 011
check: 0b101101 0b110

45 is right, but 6 gives 011 and the real answer is 110. It is backwards. Why did 45 work? Because 101101 reads the same both ways: pure luck. We wrote the remainders top to bottom, but the first remainder is the rightmost bit.

Lesson: test more than one input. One passing example proves very little.

Demo 3: the fix, for any base

Put each new digit in front of the string. That is "reading bottom to top". A digit string up to F makes it work for every base up to 16.

# decimal → any base: remainders read BOTTOM to TOP
def to_base(n, base):
    digits = "0123456789ABCDEF"
    out = ""
    while n > 0:
        out = digits[n % base] + out    # put the new digit in FRONT
        n = n // base
    return out or "0"

print("45 in base 2: ", to_base(45, 2))
print("6 in base 2:  ", to_base(6, 2))
print("45 in base 8: ", to_base(45, 8))
print("255 in base 16:", to_base(255, 16))

Output:

45 in base 2:  101101
6 in base 2:   110
45 in base 8:  55
255 in base 16: FF

One method, every base: divide by the base, read the remainders up. out or "0" handles n = 0, where the loop never runs.

Worked ladders: 2026 in base 8 and base 16

2026 ÷ 8 = 253  r 2          2026 ÷ 16 = 126  r 10 = A
 253 ÷ 8 =  31  r 5           126 ÷ 16 =   7  r 14 = E
  31 ÷ 8 =   3  r 7             7 ÷ 16 =   0  r 7
   3 ÷ 8 =   0  r 3
read up: 3752 (octal)        read up: 7EA (hex)

Remainders 10 to 15 are written as the letters A to F.

Problem 4: bits too long to read (octal and hexadecimal)

Reading ten bits aloud is like reading a ten-digit phone number 9876543210 in one go. What do we do with phone numbers? Split them: 98765 43210. Do the same with bits: group them 3 at a time or 4 at a time, then write one symbol per group.

  • 3 bits make 8 patterns (0 to 7), so groups of 3 give base 8, octal.
  • 4 bits make 16 patterns (0 to 15), so groups of 4 give base 16, hexadecimal (hex). After 9, hex uses letters: A=10, B=11, C=12, D=13, E=14, F=15.

The grouping shortcut (always from the right)

Take 1011010111. Start at the right end (the ones place). Leftover bits go on the left; pad them with zeros if you like.

bits:           1 0 1 1 0 1 0 1 1 1

groups of 3:    001 | 011 | 010 | 111
octal:            1 |   3 |   2 |   7     → 1327 (octal)

groups of 4:   0010 | 1101 | 0111
hex:              2 |    D |    7         → 2D7 (hex)

Going back is the same table in reverse: replace each octal digit with its 3 bits, or each hex digit with its 4 bits. Octal ↔ hex: go through binary (octal → bits → regroup in 4s → hex).

Digit Bits Digit Bits
0 0000 8 1000
1 0001 9 1001
2 0010 A 1010
3 0011 B 1011
4 0100 C 1100
5 0101 D 1101
6 0110 E 1110
7 0111 F 1111

For octal digits 0 to 7, use the last 3 bits of the left column (5 = 101).

Demo 4: check it with Python

n = 0b1011010111

print("binary:", bin(n))
print("octal: ", oct(n))     # groups of 3 bits
print("hex:   ", hex(n))     # groups of 4 bits

print(int("2D7", 16), int("1327", 8), n)
print(f"#{255:02X}{87:02X}{51:02X}")   # a colour: red, green, blue

Output:

binary: 0b1011010111
octal:  0o1327
hex:    0x2d7
727 727 727
#FF5733
  • 0b in front means binary, 0o means octal, 0x means hex. Python prints hex letters in lowercase; 2d7 and 2D7 are the same number.
  • All three spellings are the decimal number 727.
  • The last line is a web colour: #FF5733 is red 255, green 87, blue 51, two hex digits each. :02X means "uppercase hex, at least 2 digits, pad with 0". Programmers love hex because two hex digits are exactly one byte (8 bits).

Problem 5: fractions in binary (repeated multiplication)

After the point, binary places are halves: ½, ¼, ⅛, … (2⁻¹, 2⁻², 2⁻³). To convert a fraction, multiply by 2. The part before the point is the next bit. Keep only the fraction and repeat until nothing is left.

Step Multiply Result Bit (whole part)
1 0.625 × 2 1.25 1
2 0.25 × 2 0.5 0
3 0.5 × 2 1.0 1 (0 left: stop)

Read top to bottom: 0.101. Check: 1×½ + 0×¼ + 1×⅛ = 0.5 + 0.125 = 0.625.

Whole part: divide, read up. Fraction part: multiply, read down. Opposite operation, opposite reading order. For a mixed number like 13.625, convert each part separately and join: 1101 + .101 = 1101.101.

Demo 5: fractions in code, and 0.1 never ends

# fraction → binary: keep multiplying by 2
def frac_to_binary(x, places=12):
    out = "0."
    for _ in range(places):
        x = x * 2
        bit = int(x)          # the part before the point
        out = out + str(bit)
        x = x - bit
        if x == 0:
            break
    return out

print("0.625 ->", frac_to_binary(0.625))
print("0.1   ->", frac_to_binary(0.1))

Output:

0.625 -> 0.101
0.1   -> 0.000110011001

0.625 terminates. 0.1 repeats: 0.0 0011 0011 0011 … forever. Like ⅓ = 0.333… in decimal, ¹⁄₁₀ never ends in binary. A fraction terminates in binary only if its denominator (in lowest terms) is a power of 2 (½, ¼, ⅜, ⁵⁄₁₆ …). A computer must cut 0.1 off somewhere, which is why 0.1 + 0.2 prints 0.30000000000000004 in Python. That is episode 4.

MSB, LSB and how many bits a number needs

Place value 128 64 32 16 8 4 2 1
45 in 8 bits 0 (MSB) 0 1 0 1 1 0 1 (LSB)
  • MSB (most significant bit): the leftmost bit, the biggest place (here worth 128).
  • LSB (least significant bit): the rightmost bit, the ones place. Change it and the number changes by just 1.
  • Trick: LSB = 1 means the number is odd, because every other place is even. 45 ends in 1, so it is odd.

Demo 6: bits needed

import math

for n in [5, 255, 256, 1000]:
    print(n, "needs", n.bit_length(), "bits")

students = 1000                  # give each one a unique ID
print("IDs 0..999 need", math.ceil(math.log2(students)), "bits")

Output:

5 needs 3 bits
255 needs 8 bits
256 needs 9 bits
1000 needs 10 bits
IDs 0..999 need 10 bits

The rules:

  • n bits give 2ⁿ patterns (0 to 2ⁿ − 1). 8 bits: 256 patterns, 0 to 255.
  • To write a number N (N ≥ 1): ⌊log₂ N⌋ + 1 bits. 255 is 11111111 (8 bits); 256 is one step past eight ones and needs a new place: 9 bits.
  • To give K different things a unique code: ⌈log₂ K⌉ bits. 2¹⁰ = 1024 ≥ 1000, so 1000 students need 10 bits.

Problem 6: a clock shows digits (BCD and excess-3)

A digital clock or calculator display shows digits. To show 45 it lights up a 4 and a 5, separately. But binary 45 is 101101: no 4 and no 5 anywhere in it. To find the digits, the chip must divide by 10 again and again, which is slow work for a tiny chip. So instead, give each decimal digit its own 4 bits: 4 is 0100, 5 is 0101. This is BCD, Binary Coded Decimal.

Demo 7: BCD and excess-3

# BCD: every decimal digit gets its own 4 bits
def bcd(n):
    return " ".join(f"{int(d):04b}" for d in str(n))

def excess3(n):                    # BCD of (digit + 3)
    return " ".join(f"{int(d) + 3:04b}" for d in str(n))

print("45 binary:  ", f"{45:b}")
print("45 BCD:     ", bcd(45))
print("45 excess-3:", excess3(45))

Output:

45 binary:   101101
45 BCD:      0100 0101
45 excess-3: 0111 1000
  • BCD uses 8 bits for 45 (binary needs 6), but you read the 4 and the 5 straight off. The cost: BCD wastes patterns. 4 bits can count to 15, but a digit only goes to 9, so 1010 to 1111 are never used.
  • Excess-3 is BCD of (digit + 3): 4 → 7 = 0111, 5 → 8 = 1000.
  • Why add 3? It makes the code self-complementing: flip every bit of a digit's code and you get the code of 9 − that digit. Flip 0111 (digit 4) → 1000 (digit 5), and 9 − 4 = 5. That made subtraction easier for old calculators. Plain BCD is not self-complementing: flip 0100 (4) → 1011, which is not even a valid digit.
Digit 0 1 2 3 4 5 6 7 8 9
BCD 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001
Excess-3 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100

Problem 6, part 2: the dial that lies (Gray code)

A volume knob reports its position as 4 bits, and each bit is read by its own little sensor. Turn it from 7 to 8: 0111 becomes 1000. All four bits flip. But four sensors never flip at exactly the same instant. For a split second it might read 1111, and the volume jumps to 15: a garbage reading, caused by many bits changing at once.

The fix: a counting order where only one bit changes at each step. That order is Gray code. You get it as n XOR (n >> 1). XOR gives 1 where two bits differ and 0 where they are the same (the full story is next episode).

Demo 8: binary vs Gray code flips

# binary vs Gray code: how many bits flip from n-1 to n?
def gray(n):
    return n ^ (n >> 1)          # ^ is XOR: 1 where the bits differ

prev_b, prev_g = 0, 0
for n in range(1, 9):
    b, g = n, gray(n)
    fb = bin(prev_b ^ b).count("1")
    fg = bin(prev_g ^ g).count("1")
    print(f"{n}: binary {b:04b} flips {fb} | gray {g:04b} flips {fg}")
    prev_b, prev_g = b, g

Output:

1: binary 0001 flips 1 | gray 0001 flips 1
2: binary 0010 flips 2 | gray 0011 flips 1
3: binary 0011 flips 1 | gray 0010 flips 1
4: binary 0100 flips 3 | gray 0110 flips 1
5: binary 0101 flips 1 | gray 0111 flips 1
6: binary 0110 flips 2 | gray 0101 flips 1
7: binary 0111 flips 1 | gray 0100 flips 1
8: binary 1000 flips 4 | gray 1100 flips 1

prev ^ now has a 1 in every place that changed, so counting its 1s counts the flips. Binary flips 1, 2, 1, 3 … and all 4 at 8. Gray code flips exactly 1 bit every time, so a half-turned knob can only be off by one step. Gray code is used in rotary encoders (the position sensors in knobs and motors) and in the Karnaugh maps of episode 5.

Binary → Gray by hand

Keep the MSB. Every other Gray bit = this binary bit XOR the binary bit to its left.

binary 13:   1    1    0    1
             ↓  1^1  1^0  0^1
gray:        1    0    1    1     → 1011

Gray → binary by hand

Keep the MSB. Every other binary bit = the binary bit you just wrote XOR this Gray bit.

gray:        1    0    1    1
binary:      1  1^0=1  1^1=0  0^1=1     → 1101 = 13

The common slip: XOR-ing neighbouring Gray bits instead of the running binary bit. In code, XOR together every right shift of g:

# Gray code → binary: each binary bit = previous binary bit XOR this Gray bit
def gray(n):
    return n ^ (n >> 1)

def gray_to_binary(g):
    b = 0
    while g > 0:
        b = b ^ g        # fold in every right shift of g
        g = g >> 1
    return b

for g in ["1100", "1011", "0110"]:
    b = gray_to_binary(int(g, 2))
    print(f"gray {g} -> binary {b:04b} = {b}   back to gray: {gray(b):04b}")

print(all(gray_to_binary(gray(n)) == n for n in range(1024)))

Output:

gray 1100 -> binary 1000 = 8   back to gray: 1100
gray 1011 -> binary 1101 = 13   back to gray: 1011
gray 0110 -> binary 0100 = 4   back to gray: 0110
True

The last line checks the round trip for every number from 0 to 1023.

Common mistakes (and the real errors)

Mistake Code / work Error or wrong result Fix
Grouping from the left 1011 \| 0101 \| 11 → B53 Wrong: the real hex is 2D7 (B53 is 2899, not 727) Always group from the right; leftovers go on the left
A digit too big for the base int("129", 8) ValueError: invalid literal for int() with base 8: '129' Base b uses digits 0 to b−1
Same slip in binary int("12", 2) ValueError: invalid literal for int() with base 2: '12' Binary digits are only 0 and 1
Forgetting the base int("FF") ValueError: invalid literal for int() with base 10: 'FF' int("FF", 16) gives 255
Reading hex places as tens 0x1F read as "1 and 15" = 115 Wrong: 0x1F = 1×16 + 15 = 31 Weighted sum with powers of 16
Remainders read top to bottom to_binary(6) 011 (should be 110) Read the remainders bottom to top
Fraction bits read bottom to top 0.375 → bits 0, 1, 1 written as 0.110 Wrong: 0.110 is 0.75; the answer is 0.011 Fraction bits: read top to bottom
bin() on a fraction bin(0.5) TypeError: 'float' object cannot be interpreted as an integer Use repeated multiplication (frac_to_binary)
BCD confused with binary BCD 45 written as 101101 Wrong: BCD 45 is 0100 0101 BCD codes each decimal digit in 4 bits
Gray with the wrong shift 10 ^ (10 << 1) 30, not a 4-bit Gray code Shift right: 10 ^ (10 >> 1) = 15 = 1111

The octal error in full:

int("129", 8)
Traceback (most recent call last):
  File "main.py", line 1, in <module>
    int("129", 8)
    ~~~^^^^^^^^^^
ValueError: invalid literal for int() with base 8: '129'

Mini project: a universal base converter

One program that combines everything: repeated division for the whole part, repeated multiplication for the fraction, the weighted sum to come back, and a clear error for a bad digit. It works for any base from 2 to 16.

# Universal base converter: whole numbers AND fractions, bases 2 to 16
DIGITS = "0123456789ABCDEF"

def to_base(x, base, places=10):
    whole = int(x)
    frac = x - whole
    out = ""
    while whole > 0:                       # repeated division, read up
        out = DIGITS[whole % base] + out
        whole = whole // base
    out = out or "0"
    if frac > 0:
        out = out + "."
        for _ in range(places):            # repeated multiplication, read down
            frac = frac * base
            d = int(frac)
            out = out + DIGITS[d]
            frac = frac - d
            if frac == 0:
                break
    return out

def from_base(s, base):
    s = s.upper()
    whole, _, frac = s.partition(".")
    total = 0
    for ch in whole:                       # weighted sum, left to right
        d = DIGITS.index(ch)
        if d >= base:
            raise ValueError(f"digit {ch!r} is not allowed in base {base}")
        total = total * base + d
    for i, ch in enumerate(frac, start=1): # places after the point: base^-1, base^-2 ...
        d = DIGITS.index(ch)
        if d >= base:
            raise ValueError(f"digit {ch!r} is not allowed in base {base}")
        total = total + d * base ** -i
    return total

for n in [45, 255, 727, 2026]:
    print(f"{n:>5}: bin {to_base(n, 2):>12}  oct {to_base(n, 8):>5}  hex {to_base(n, 16):>4}")

print("13.625 in base 2:", to_base(13.625, 2))
print("0.1 in base 2:   ", to_base(0.1, 2))
print("0.5 in base 8:   ", to_base(0.5, 8))
print("1101.101 (2) =", from_base("1101.101", 2))
print("2D7 (16)     =", from_base("2D7", 16))
print("17.4 (8)     =", from_base("17.4", 8))
print("check:", from_base(to_base(2026, 7), 7))
try:
    from_base("129", 8)
except ValueError as e:
    print("error:", e)

Output:

   45: bin       101101  oct    55  hex   2D
  255: bin     11111111  oct   377  hex   FF
  727: bin   1011010111  oct  1327  hex  2D7
 2026: bin  11111101010  oct  3752  hex  7EA
13.625 in base 2: 1101.101
0.1 in base 2:    0.0001100110
0.5 in base 8:    0.4
1101.101 (2) = 13.625
2D7 (16)     = 727
17.4 (8)     = 15.5
check: 2026
error: digit '9' is not allowed in base 8

total = total * base + d is the weighted sum done left to right (Horner's way): for 2D7, ((2)×16 + 13)×16 + 7 = 727. The check line converts 2026 to base 7 and back. Extend it: add Gray code and BCD output, or accept a 0b/0o/0x prefix.

Practice

Do each by hand first, then check in Python.

  1. Convert 2026 to binary, octal and hex (the episode homework).
  2. Convert 156 to binary using the division ladder.
  3. Convert 100 to octal and 3000 to hex.
  4. Convert hex 3A7 and octal 745 to decimal.
  5. Convert octal 745 to hex without going through decimal.
  6. Convert binary 10101010 to octal, hex and decimal.
  7. Convert 0.375 and 0.8125 to binary.
  8. Convert 10.25 to binary, and binary 110101.11 to decimal.
  9. Convert 0.2 to binary. Does it terminate?
  10. How many bits does each need: 1023, 1024, 4096?
  11. How many bits for 5000 unique IDs? For 300? For 26 letters?
  12. Write 2026 and 739 in BCD.
  13. Write 59 in excess-3, and show the self-complementing property on digit 2.
  14. Find the Gray code of 13, 10 and 15.
  15. Convert Gray 1111 and 1001 to binary.
  16. Which is larger: 0x1F, 0o37 or 0b11110?
Solutions and hints

1. Binary ladder remainders (2026, 1013, 506, 253, 126, 63, 31, 15, 7, 3, 1): 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1. Read up: 11111101010. Octal: group 3 from the right: 11 111 101 010 → 3752. Hex: group 4: 111 1110 1010 → 7EA. Python: bin(2026), oct(2026), hex(2026) → 0b11111101010 0o3752 0x7ea.

2. 156 → 78 r 0 → 39 r 0 → 19 r 1 → 9 r 1 → 4 r 1 → 2 r 0 → 1 r 0 → 0 r 1. Read the remainders up: 10011100.

3. 100 ÷ 8 = 12 r 4, 12 ÷ 8 = 1 r 4, 1 ÷ 8 = 0 r 1 → 144 (octal). 3000 ÷ 16 = 187 r 8, 187 ÷ 16 = 11 r 11 (B), 11 ÷ 16 = 0 r 11 (B) → BB8 (hex).

4. 3A7 = 3×256 + 10×16 + 7 = 768 + 160 + 7 = 935. 745 (octal) = 7×64 + 4×8 + 5 = 448 + 32 + 5 = 485.

5. Octal → bits: 7 = 111, 4 = 100, 5 = 101 → 111100101. Regroup in 4s from the right: 1 1110 0101 → 1E5 (hex). Check: 1×256 + 14×16 + 5 = 485.

6. Octal: 10 101 010 → 252. Hex: 1010 1010 → AA. Decimal: 128 + 32 + 8 + 2 = 170.

7. 0.375: ×2 = 0.75 (0), ×2 = 1.5 (1), 0.5 ×2 = 1.0 (1) → 0.011. 0.8125: 1.625 (1), 1.25 (1), 0.5 (0), 1.0 (1) → 0.1101.

8. 10 = 1010, 0.25 = .01 → 1010.01. 110101.11 = 32 + 16 + 4 + 1 + ½ + ¼ = 53.75.

9. 0.2 → 0.4 (0), 0.8 (0), 1.6 (1), 1.2 (1), 0.4 (0) … back to 0.4, so it loops: 0.0011 0011 0011 … It never terminates (denominator 5 is not a power of 2).

10. 1023 = ten 1s: 10 bits. 1024 = 2¹⁰ needs a new place: 11 bits. 4096 = 2¹²: 13 bits. (⌊log₂ N⌋ + 1; n.bit_length() agrees.)

11. 5000: 2¹² = 4096 < 5000 ≤ 8192 = 2¹³ → 13 bits. 300: 2⁹ = 512 → 9 bits. 26 letters: 2⁵ = 32 → 5 bits.

12. 2026 → 0010 0000 0010 0110. 739 → 0111 0011 1001.

13. 5 + 3 = 8 → 1000, 9 + 3 = 12 → 1100, so 59 = 1000 1100. Digit 2 in excess-3 is 0101; flip all bits → 1010 = 10 − 3 = digit 7, and 9 − 2 = 7.

14. 13 = 1101 → 1011. 10 = 1010 → 1, 1^0=1, 0^1=1, 1^0=1 → 1111. 15 = 1111 → 1000.

15. Gray 1111: 1, 1^1=0, 0^1=1, 1^1=0 → 1010 (10). Gray 1001: 1, 1^0=1, 1^0=1, 1^1=0 → 1110 (14).

16. 0x1F = 31, 0o37 = 3×8 + 7 = 31, 0b11110 = 30. So 0x1F and 0o37 tie at 31; 0b11110 is smaller.

Quick quiz

Binary 11011110: what is it in hexadecimal?

  • A. 0xDE
  • B. 0x3336
  • C. 0xED
  • D. 0x222
Answer

A, 0xDE. Group 4 bits from the right: 1101 | 1110 = D | E. D (0x222) is a trap: 222 is the decimal value (128 + 64 + 16 + 8 + 4 + 2), not hex. C puts the two groups in the wrong order.

Interview questions

  • What is the base (radix) of a number system? The number of distinct digits it uses; base b has digits 0 to b−1 and places b⁰, b¹, b² …
  • How do you convert any base to decimal? The weighted sum: each digit × its place value, added up.
  • How do you convert decimal to base b? Repeated division by b; read the remainders from last to first.
  • Why do octal and hex map so neatly to binary? 8 = 2³ and 16 = 2⁴, so each octal digit is exactly 3 bits and each hex digit exactly 4 bits.
  • How do you convert octal to hex? Go through binary: expand each octal digit to 3 bits, regroup in 4s from the right.
  • How do you convert a decimal fraction to binary? Repeated multiplication by 2; the whole parts, read top to bottom, are the bits.
  • Why can't 0.1 be stored exactly in binary? Its denominator 10 has a factor 5, not only 2s, so the binary expansion repeats forever and must be cut off.
  • How many bits are needed to represent N? To give K items unique codes? ⌊log₂ N⌋ + 1; ⌈log₂ K⌉.
  • What are MSB and LSB? How can the LSB tell you if a number is odd? Leftmost (biggest place) and rightmost (ones place) bit; LSB = 1 means odd.
  • What is BCD, and what is its drawback? Each decimal digit in 4 bits; it wastes 6 of the 16 patterns and needs more bits than binary.
  • What is excess-3 and why is it self-complementing? BCD of digit + 3; flipping all bits of a digit's code gives the code of 9 − digit.
  • What is Gray code and where is it used? An order where consecutive values differ in exactly one bit; rotary encoders and Karnaugh maps. Binary → Gray is n ^ (n >> 1).
  • How do you convert Gray code back to binary? Keep the MSB; each next binary bit = previous binary bit XOR the current Gray bit.

Glossary

Term Meaning Example
Digit One symbol used to write a number In 472, the digits are 4, 7 and 2
Positional notation Writing numbers so a digit's value depends on where it sits The 2 in 240 means two hundreds
Place value What one unit in a position is worth In decimal: 1, 10, 100; in binary: 1, 2, 4, 8
Radix / base How many different digits a system uses; each place is base times the one on its right Decimal is base 10 (0-9), binary base 2 (0, 1)
Binary Base 2: digits 0 and 1, places 1, 2, 4, 8 … 101101 = 45
Octal Base 8: digits 0 to 7; one octal digit = 3 bits 55 (octal) = 45
Decimal Base 10: the everyday system, digits 0 to 9 45
Hexadecimal (hex) Base 16: digits 0-9 then A-F (10-15); one hex digit = 4 bits 2D (hex) = 45; colour #FF5733
Bit One binary digit, 0 or 1 101101 has 6 bits
Byte A group of 8 bits; exactly two hex digits FF = 11111111 = 255
Weighted sum Converting to decimal by adding digit × place value 101101 = 32 + 8 + 4 + 1 = 45
Repeated division Converting decimal to base b: divide by b again and again, keep the remainders, read them bottom to top 6 → remainders 0, 1, 1 → 110
Quotient The whole-number answer of a division 45 ÷ 2 = 22 remainder 1; quotient 22
Remainder What is left over after dividing; Python's % 45 % 2 = 1
Grouping shortcut Binary to octal/hex by splitting bits into groups of 3/4 from the right, one digit per group 1011010111 → 1 011 010 111 → 1327
Repeated multiplication (fractional conversion) Converting a fraction to base b: multiply by b, take the whole part as the next digit, keep the fraction, repeat; read top to bottom 0.625 → 1, 0, 1 → 0.101
Terminating fraction A fraction whose digits stop; in binary only when the denominator is a power of 2 0.625 = ⅝ = 0.101
Repeating fraction A fraction whose digits go on forever in a pattern 0.1 = 0.0001100110011…
MSB (most significant bit) The leftmost bit, in the biggest place In 00101101, the MSB is worth 128
LSB (least significant bit) The rightmost bit, the ones place; 1 means odd 45 = …101, LSB 1, so odd
Bits needed for N ⌊log₂ N⌋ + 1 bits write a number N ≥ 1; Python's n.bit_length() 255 → 8 bits, 256 → 9 bits
Bits for K unique codes ⌈log₂ K⌉ bits give K things different codes, since n bits give 2ⁿ patterns 1000 students → 10 bits (2¹⁰ = 1024)
floor ⌊x⌋ / ceil ⌈x⌉ Round down / round up to a whole number ⌊9.97⌋ = 9, ⌈9.97⌉ = 10
log₂ "2 to what power gives this?" log₂ 1024 = 10
bit_length() Python method: how many bits a whole number needs (1000).bit_length() → 10
0b / 0o / 0x prefixes Marks in front of a number saying its base: binary, octal, hex 0b101 = 5, 0o17 = 15, 0x1F = 31
bin() / oct() / hex() Python functions that turn a whole number into a binary/octal/hex string with its prefix hex(255) → '0xff'
int(s, base) Python function that reads string s as a number in the given base int("2D7", 16) → 727
BCD (Binary Coded Decimal) Each decimal digit stored separately in 4 bits 45 → 0100 0101
Excess-3 code BCD of (each digit + 3) 45 → 0111 1000
Self-complementing code A code where flipping every bit gives the code of 9 − digit Excess-3: 4 = 0111 → flip → 1000 = 5
Gray code A counting order where neighbouring values differ in exactly one bit; n ^ (n >> 1) 7 = 0100, 8 = 1100 (one flip)
Gray to binary Keep the MSB; each next binary bit = previous binary bit XOR this Gray bit Gray 1011 → binary 1101 = 13
XOR (^) Exclusive OR: gives 1 where two bits differ, 0 where they are the same 0111 ^ 1000 = 1111 (4 bits changed)
Right shift (>>) Moves all bits one place right, dropping the LSB (halves, rounding down) 13 >> 1 = 6 (1101 → 110)
Rotary encoder A sensor that reports how far a knob or motor shaft has turned A volume knob sending its position as bits
ValueError Python's error for a value of the right type but wrong content int("129", 8): 9 is not an octal digit
TypeError Python's error for a value of the wrong type bin(0.5): floats are not allowed

Summary

  • Positional notation: a digit's value = digit × place value. The base is how many digits exist; base b uses 0 to b−1.
  • To decimal: the weighted sum. From decimal: repeated division, read the remainders up (test more than one input!).
  • Octal = groups of 3 bits, hex = groups of 4 bits, always grouped from the right. Two hex digits = one byte.
  • Fractions: repeated multiplication, read down. 0.1 repeats forever in binary.
  • MSB = leftmost, LSB = rightmost; N needs ⌊log₂ N⌋ + 1 bits, K codes need ⌈log₂ K⌉ bits.
  • BCD = 4 bits per decimal digit; excess-3 = BCD + 3, self-complementing; Gray code = one bit flips per step, n ^ (n >> 1).

Conversion cheat sheet

From → To Method Example
Base b → decimal Weighted sum: digit × bᵖˡᵃᶜᵉ, add 2D7 → 2×256 + 13×16 + 7 = 727
Decimal → base b Divide by b, read remainders bottom to top 45 → 101101, 55 (oct), 2D (hex)
Decimal fraction → base b Multiply by b, read whole parts top to bottom 0.625 → 0.101
Binary → octal Groups of 3 bits from the right 1 011 010 111 → 1327
Binary → hex Groups of 4 bits from the right 10 1101 0111 → 2D7
Octal / hex → binary Each digit → 3 / 4 bits 7EA → 0111 1110 1010
Octal ↔ hex Go through binary, regroup 745 (oct) → 111100101 → 1E5
Decimal → BCD Each digit → 4 bits 45 → 0100 0101
Decimal → excess-3 Each digit + 3 → 4 bits 45 → 0111 1000
Binary → Gray n ^ (n >> 1); keep MSB, XOR neighbours 1101 → 1011
Gray → binary Keep MSB, XOR running binary bit with next Gray bit 1011 → 1101
Python bin, oct, hex, int(s, base), f"{n:b}", f"{n:02X}" int("1327", 8) → 727

Next episode: a bank balance can be −500, but there is no minus sign in a bit. We invent sign-magnitude, watch it fail, and end up at two's complement, plus binary addition, overflow and bitwise operators.