Day 6 — Positional bases

Day 6 — Positional bases

Stage I · concept day
Goal: Interpret place-value polynomials in any base \(b\ge 2\); convert among bases \(2\)–\(16\); map hex↔︎binary by nibbles; validate digits; evaluate with Horner’s method.

Why this matters

Computers are binary; humans often debug in hex. Network addresses, color codes, bitmasks, and file offsets are base-fluent tasks. Place value is the same idea as decimal—only the radix changes.

Theory

Place-value polynomial

Fix an integer base (radix) \(b\ge 2\). Digits \(d_i\) satisfy \(0\le d_i<b\). A finite representation

\[(d_n d_{n-1}\ldots d_1 d_0)_b\]

means the integer

\[N=\sum_{i=0}^{n} d_i\, b^{i}=d_n b^{n}+d_{n-1}b^{n-1}+\cdots+d_1 b+d_0.\]

Examples: \((1011)_2=8+2+1=11_{10}\).
\((2A)_{16}=2\cdot 16+10=42_{10}\).

Fractional part \((0.d_{-1}d_{-2}\ldots)_b=\sum_{k\ge 1}d_{-k}b^{-k}\) exists but we focus on integers unless needed.

Digit symbols for bases up to \(16\)

Value	Symbol
\(0\)–\(9\)	0–9
\(10\)	A (or a)
\(11\)	B
\(12\)	C
\(13\)	D
\(14\)	E
\(15\)	F

Digit validity: in base \(b\), every digit must be in \(\{0,1,\ldots,b-1\}\).
\((2A)_{16}\) OK; \((2A)_8\) invalid (A is not a digit in base \(8\)).
\((18)_8\) invalid because digit \(8\not< 8\).

Horner’s method (evaluation)

Rewrite \[N=d_0+b(d_1+b(d_2+b(\cdots+b d_n)\cdots)).\]

Algorithm: start acc = 0; for digits from most significant to least: acc = acc * b + next_digit.

Horner minimizes multiplications and is how parseInt style conversions often work. Same idea as polynomial evaluation (Day 15).

Conversion: base \(b\) → decimal

Expand place values or run Horner with base \(b\).

Conversion: decimal → base \(b\)

Repeated division: while \(N>0\): remainder \(N\bmod b\) is the next least significant digit; replace \(N\leftarrow\lfloor N/b\rfloor\). Then reverse remainders to write MSD-first.

Example: \(42\) to binary:
\(42=2\cdot 21+0\), \(21=2\cdot 10+1\), \(10=2\cdot 5+0\), \(5=2\cdot 2+1\), \(2=2\cdot 1+0\), \(1=2\cdot 0+1\).
Remainders LSB→MSB: \(0,1,0,1,0,1\) → reverse → \((101010)_2\).

Binary ↔︎ hexadecimal (nibble map)

One hex digit \(=4\) bits (a nibble), because \(16=2^4\).

Hex	Binary	Hex	Binary
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

Binary → hex: pad left to multiple of \(4\) bits; replace each group.
Hex → binary: replace each hex digit by its \(4\)-bit pattern.

Binary ↔︎ octal: groups of \(3\) bits (\(8=2^3\)).

Conversion between arbitrary bases

Common path: base \(b_1\) → decimal → base \(b_2\).
Or: if both powers of two, regroup bits (bin/oct/hex).

Range of \(k\)-digit strings

In base \(b\), \(k\)-digit strings (allowing leading zeros) represent \(0,1,\ldots,b^k-1\) — exactly \(b^k\) values.
Without leading zeros, largest \(k\)-digit number is \(b^k-1\).

Worked examples

Example 1 — Expand binary

\((110101)_2=32+16+4+1=53_{10}\).

Example 2 — Horner binary

Digits \(1,1,0,1,0,1\):
\(0\cdot 2+1=1\)
\(1\cdot 2+1=3\)
\(3\cdot 2+0=6\)
\(6\cdot 2+1=13\)
\(13\cdot 2+0=26\)
\(26\cdot 2+1=53\).

Example 3 — Decimal to hex

\(255\) to hex: \(255=15\cdot 16+15\) → digits F,F → (FF)\(_{16}\).
\(256=(100)_{16}\).

Example 4 — Hex to decimal

(C0FFEE)\(_{16}\) is large; smaller: (2F)\(_{16}=2\cdot 16+15=47\).

Example 5 — Nibble convert

\((1010\,1111\,0001)_2\) → group 1010 1111 0001 → A F 1 → (AF1)\(_{16}\).

Example 6 — Hex to binary

(7B)\(_{16}\) → 0111 1011 → \((1111011)_2\) (drop leading zero if desired).

Example 7 — Octal

\((157)_8=1\cdot 64+5\cdot 8+7=111_{10}\).
Binary via 3-bit: \(001\) \(101\) \(111\) → \((1101111)_2\).

Example 8 — Invalid digits

Is \((308)_8\) valid? Digit \(8\) invalid. \((G1)_{16}\) invalid. \((1012)_2\) invalid digit \(2\).

Example 9 — Base \(5\)

\((243)_5=2\cdot 25+4\cdot 5+3=73_{10}\).
Convert \(73\) to base \(5\): \(73=2\cdot 25+23\), \(23=4\cdot 5+3\) → wait systematic:
\(73=14\cdot 5+3\), \(14=2\cdot 5+4\), \(2=0\cdot 5+2\) → \((243)_5\).

Example 10 — Count values

\(8\)-bit strings: \(2^8=256\) values \(0..255\).
\(2\)-digit hex: \(16^2=256\) values — same count as \(8\) bits.

Example 11 — Color

#FF8800 → \(R=(FF)_{16}=255\), \(G=(88)_{16}=136\), \(B=(00)_{16}=0\).

Example 12 — Mixed base chain

\((1A)_{16}\to\) binary 0001 1010 \(\to\) octal groups 00 011 010 \(= (032)_8= (32)_8\).

Example 13 — Horner hex

(3E8)\(_{16}\): digits \(3,14,8\):
\(0\cdot 16+3=3\), \(3\cdot 16+14=62\), \(62\cdot 16+8=1000_{10}\). (Indeed \(1000=3\cdot 256+14\cdot 16+8\).)

Example 14 — Why pad bits

\((1111)_2=(F)_{16}\). Without padding, grouping \((1\,111)\) wrong if you split as \(1\) and \(111\). Always pad MSD side to full nibble.

Exercises

Easy

1. Convert \((10110)_2\) to decimal.
2. Convert \(45_{10}\) to binary.
3. Convert \((2C)_{16}\) to decimal and to binary.
4. Which are invalid? \((19)_8\), \((19)_{16}\), \((102)_2\), \((AB)_{10}\).
5. Map BEEF hex to binary (each digit).

Medium

6. Convert \(1000_{10}\) to hex using repeated division.
7. Convert \((345)_6\) to decimal; then to base \(4\).
8. Evaluate \((11011101)_2\) by Horner; check by place values.
9. Convert \((777)_8\) to binary and hex.
10. How many distinct values do \(k\)-digit base-\(b\) strings (leading zeros allowed) represent?
11. Write \(2^{10}-1\) in binary and hex.
12. Convert \((0.1)_2\) to a decimal fraction (optional fractional practice).
13. Express \(255\) and \(256\) in binary, octal, and hex.

Hard

14. Prove that the repeated-division algorithm yields correct digits (uniqueness of base-\(b\) expansion for \(N\ge 0\)).
15. Show every nonnegative integer has a unique representation in base \(b\) without leading zeros (except \(0\) itself).
16. Convert \((1A3)_{16}\) to base \(7\) (via decimal).
17. Explain why binary↔︎hex needs groups of \(4\), not \(3\).
18. What is the largest \(4\)-digit number in base \(b\)? In decimal?
19. Horner: count multiplications to evaluate an \(n\)-digit base-\(b\) numeral vs naive powers.
20. Show \((d_n\ldots d_0)_b < b^{n+1}\).

Challenge / CS-flavored

21. IPv4 address bytes as decimal vs hex dump: \(192.168.0.1\) — write each octet in hex.
22. Bitmask 0xF0 in binary; which bit positions (0-based from LSB) are set?
23. Parse algorithm: implement Horner by hand for string "1F" base \(16\).
24. Why do programmers prefer hex over decimal for \(32\)-bit patterns?
25. Base \(64\) uses \(64\) symbols (not computed in detail): how many bits per digit conceptually?

Uniqueness of representation

Theorem. Fix base \(b\ge 2\). Every integer \(N\ge 0\) has a unique sequence of digits \(0\le d_i<b\) with \(d_n\neq 0\) if \(N>0\) such that \(N=\sum_{i=0}^{n} d_i b^{i}\).

Proof sketch. Existence by repeated division. Uniqueness: if two expansions equal, subtract; smallest differing digit would imply \(b\) divides a digit difference with absolute value \(<b\), forcing difference \(0\). \(\square\)

Fractional bases (brief)

\((0.d_{-1}d_{-2}\ldots d_{-m})_b=\sum_{k=1}^{m} d_{-k} b^{-k}\).
Binary fractions: \((0.11)_2=\frac{1}{2}+\frac{1}{4}=\frac{3}{4}\).
Terminating in base \(b\) relates to denominators dividing a power of \(b\) (Day 3 analogue).

Mixed-radix note

Time (hours/minutes/seconds) is mixed radix \(24\)–\(60\)–\(60\), not pure base—but place-value thinking still applies with varying weights.

Horner complexity

Degree-\(n\) (or \(n+1\) digits): \(n\) multiplications by \(b\) and \(n\) additions. Naive \(\sum d_i b^i\) with fresh powers can use more multiplies unless powers are cached.

Conversion drills (worked)

Drill. \(1000_{10}\) to binary: repeated \(\div 2\) → \((1111101000)_2\). Hex: \(1000=3\cdot 256+232\), \(232=14\cdot 16+8\) → (3E8)\(_{16}\).
Drill. (DEAD)\(_{16}\) → binary nibble string 1101 1110 1010 1101.
Drill. Invalid: (2G)\(_{16}\), (18)_8, (210)_2.

Extra exercises

26. Prove uniqueness of base-\(b\) digits for \(N\ge 0\) (write the difference argument carefully).
    
27. Convert \((0.001)_2\) and \((0.1)_{16}\) to decimal fractions.
    
28. Express \(2^{16}-1\) in hex and binary.
    
29. How many hex digits are needed for all \(32\)-bit patterns (including leading zeros as fixed width)?
    
30. Parse "FF" with Horner in base \(16\) step by step; repeat in base \(15\) with digit values—why base \(15\) digit F is invalid.

CS connection

Memory dumps, HTML colors, Unicode code points (U+1F600), machine code, and MAC addresses are hex-heavy. Binary is the hardware truth; octal still appears in Unix file modes (0755). Horner’s method is polynomial evaluation—same as efficient x^n accumulation patterns. Validating digits is input sanitation for parsers.

Common pitfalls

Pitfall	What to do instead
Reading hex as decimal	Expand powers of \(16\)
Wrong nibble grouping	Pad to multiples of \(4\) from the left
Invalid digits	Enforce \(0\le d<b\)
Remainder order reversed	LSB is first remainder; reverse for writing
Assuming unique length	Leading zeros do not change value
Base \(b\) digit $b$	Digits only to \(b-1\)

End-of-day synthesis problems

S1. Convert \(365_{10}\) to binary, octal, and hex.

S2. Horner-evaluate (BEEF)\(_{16}\) to decimal (you may compute stepwise).

S3. Convert (1011 1100 0001 1111)_2 to hex by nibbles.

S4. Which are valid? (1A)_12, (1A)_10, (70)_8, (70)_7.

S5. Prove every \(N\) with \(0\le N<b^{k}\) has a unique \(k\)-digit base-\(b\) representation allowing leading zeros.

S6. Explain why \(16^{2}=256=2^{8}\) means two hex digits match one byte.

S7. Convert \((144)_{5}\) to base \(3\) via decimal.

S8. Color #C0FFEE: write RGB decimal triples.

Checkpoint

• Expand any base-\(b\) numeral via \(\sum d_i b^i\)
  
• Convert decimal \(\leftrightarrow\) base \(b\) by division/Horner
  
• Convert binary \(\leftrightarrow\) hex by nibbles fluently
  
• Detect invalid digit strings
  
• State how many values \(k\) digits in base \(b\) encode
  
• Finish S1–S4 timed (15 minutes)

Write two takeaways in your own words.

Deep dive — place value, Horner, nibble fluency

D1 — Repeated division to hex (worked fully).
Convert \(365_{10}\) to hex:
\(365=22\cdot 16+13\),
\(22=1\cdot 16+6\),
\(1=0\cdot 16+1\).
Digits LSB-first \(13,6,1\) → reverse → (16D)\(_{16}\).
Check: \(1\cdot 256+6\cdot 16+13=256+96+13=365\).

D2 — Binary to hex with padding discipline.
\((11011110101)_2\): pad left to multiple of \(4\): \(0110\,1111\,0101\) → 6 F 5 → (6F5)\(_{16}\).
Mis-grouping from the right without padding the left is the classic error when bit length \(\not\equiv 0\pmod 4\).

D3 — Horner in base \(7\).
\((254)_7\): \(0\cdot 7+2=2\), \(2\cdot 7+5=19\), \(19\cdot 7+4=137_{10}\).
Place values: \(2\cdot 49+5\cdot 7+4=98+35+4=137\).

D4 — Arbitrary base path.
\((144)_5\to\) decimal \(1\cdot 25+4\cdot 5+4=49\), then \(49\) to base \(3\):
\(49=16\cdot 3+1\), \(16=5\cdot 3+1\), \(5=1\cdot 3+2\), \(1=0\cdot 3+1\) → \((1211)_3\).

D5 — Range counts that match bit widths.
\(12\)-bit unsigned: \(2^{12}=4096\) values.
\(3\) hex digits: \(16^3=4096\) — same cardinality; fixed-width hex dump of a \(12\)-bit field uses \(3\) digits (sometimes written with a leading nibble share in \(16\)-bit words).

D6 — Invalid digit detection algorithm (mental).
Scan each character; map 0–9,A–F to values; reject if value \(\ge b\).
(2G)\(_{16}\) fails on G; (70)_7 fails on digit 7; (102)_2 fails on 2.

Extra practice set

31. Convert \(1000_{10}\) to binary, octal, and hex; verify hex via nibbles from binary.
    
32. Horner-evaluate (C0DE)\(_{16}\) to decimal (stepwise accumulation).
    
33. Convert (775)_8 to binary by \(3\)-bit groups, then to hex by \(4\)-bit groups.
    
34. Prove uniqueness sketch: if two base-\(b\) expansions of \(N\) differ, derive a contradiction from digit bounds.
    
35. How many distinct values do \(4\)-digit base-\(5\) strings represent (leading zeros allowed)?

Tomorrow

Day 7 — Binary arithmetic & two’s complement. Add/sub, \(n\)-bit two’s complement range, overflow, bitwise ops as integer ideas, shifts as \(\times 2\) / \(\div 2\).