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
0bin front means binary,0omeans octal,0xmeans hex. Python prints hex letters in lowercase;2d7and2D7are the same number.- All three spellings are the decimal number 727.
- The last line is a web colour:
#FF5733is red 255, green 87, blue 51, two hex digits each.:02Xmeans "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
1010to1111are 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: flip0100(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.
- Convert 2026 to binary, octal and hex (the episode homework).
- Convert 156 to binary using the division ladder.
- Convert 100 to octal and 3000 to hex.
- Convert hex
3A7and octal745to decimal. - Convert octal
745to hex without going through decimal. - Convert binary
10101010to octal, hex and decimal. - Convert 0.375 and 0.8125 to binary.
- Convert 10.25 to binary, and binary
110101.11to decimal. - Convert 0.2 to binary. Does it terminate?
- How many bits does each need: 1023, 1024, 4096?
- How many bits for 5000 unique IDs? For 300? For 26 letters?
- Write 2026 and 739 in BCD.
- Write 59 in excess-3, and show the self-complementing property on digit 2.
- Find the Gray code of 13, 10 and 15.
- Convert Gray
1111and1001to binary. - Which is larger:
0x1F,0o37or0b11110?
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.