Binary and Hexadecimal Representation

A positional number system represents a nonnegative integer as a sequence of digits $d_{n-1} d_{n-2} \cdots d_1 d_0$, each drawn from a fixed alphabet of size $b$ (the base or radix), whose value is defined by

Decimal ($b=10$) uses digits $\{0,\dots,9\}$. Binary ($b=2$) uses only $\{0,1\}$; each digit is called a bit (binary digit), and it maps directly onto a two-state physical device — a transistor that is on or off, a capacitor that is charged or not, a magnetic domain polarized one way or the other. This is precisely why binary, not decimal, is the native language of digital circuits: building a reliable device with ten distinguishable voltage levels is far harder than building one that only needs to distinguish "high" from "low."

Hexadecimal ($b=16$) uses sixteen digit symbols: $0$–$9$ for the values zero through nine, and the letters $A$–$F$ (or lowercase $a$–$f$) for the values ten through fifteen, since standard notation has no single symbol for a "digit" above 9. Hexadecimal is never implemented in hardware directly — no wire has sixteen voltage levels. Its entire purpose is human ergonomics: writing out a 32-bit binary number like `10110100111000010100101011110000` is error-prone to read and transcribe, while its hex equivalent `B4E14AF0` is eight characters, easy to chunk, and (as shown below) trivially recoverable back into the exact same bits. The key structural fact tying the two together is that $16 = 2^4$. Because each hex digit represents a value from 0 to 15, and every such value has a unique 4-bit binary representation, one hex digit always corresponds to exactly four bits — no more, no less. This "nibble" correspondence is what makes binary–hex conversion a table lookup rather than an arithmetic computation, in sharp contrast to binary–decimal conversion, which genuinely requires division and multiplication because 10 is not a power of 2.

There are three conversions worth mastering: decimal → binary, decimal → hexadecimal, and binary ↔ hexadecimal. The first two share an algorithm ("repeated division"); the third is a direct regrouping.

Repeated division algorithm. To convert a decimal integer $N$ into base $b$, repeatedly divide $N$ by $b$, recording the remainder at each step; the remainders, read from last to first, form the digit string. ``` ALGORITHM ConvertToBase(N, b) // N: nonnegative decimal integer, b: target base (b >= 2) if N == 0: return "0" // base case: zero is its own representation digits = empty list while N > 0: r = N mod b // remainder is the next least-significant digit digits.append(DigitSymbol(r)) // map 0-9 -> '0'-'9', 10-15 -> 'A'-'F' for hex N = N div b // integer division: strip off that digit's weight reverse(digits) // remainders came out least-significant first return concatenate(digits) ```

Why the remainders are the digits. Write $N$ in base $b$ as $N = d_{n-1}b^{n-1} + \cdots + d_1 b + d_0$. Then

because every term except $d_0$ is a multiple of $b$. So dividing by $b$ once "peels off" $d_0$ as the remainder and leaves exactly the number formed by the remaining, higher-order digits — the same problem, one digit smaller. Repeating this until the quotient reaches 0 recovers every digit, from least significant to most significant, which is why the collected remainders must be reversed at the end.

Binary ↔ hexadecimal via nibble grouping. Because $16^1 = 2^4$, each hex digit is worth exactly 4 bits. To go binary → hex, pad the bit string on the left with zeros until its length is a multiple of 4, split it into groups of 4 starting from the right, and translate each group independently using the 4-bit table below. To go hex → binary, reverse the process: replace each hex digit with its fixed 4-bit pattern and concatenate. ``` ALGORITHM BinaryToHex(bits) // bits: string of '0'/'1', most significant bit first pad_len = (4 - length(bits) mod 4) mod 4 bits = "0" * pad_len + bits // left-pad to a multiple of 4 groups = split bits into chunks of 4, left to right result = "" for each group g in groups: value = binary_value(g) // 0..15, computed from the 4 bits directly result = result + HexSymbol(value) return result ALGORITHM HexToBinary(hexstr) result = "" for each character c in hexstr: v = HexDigitValue(c) // '0'-'9','A'-'F' -> 0..15 result = result + FourBitBinary(v) // fixed 4-bit pattern, no arithmetic return result ``` The 4-bit lookup table used by both directions: ``` Hex Binary Decimal 0 0000 0 1 0001 1 2 0010 2 3 0011 3 4 0100 4 5 0101 5 6 0110 6 7 0111 7 8 1000 8 9 1001 9 A 1010 10 B 1011 11 C 1100 12 D 1101 13 E 1110 14 F 1111 15 ```

Why grouping works, precisely. Split an $n$-bit binary string (padded to a multiple of 4) into groups $G_{k-1}, \dots, G_1, G_0$ of 4 bits each, so bit position $i$ within the whole number lives in group $\lfloor i/4 \rfloor$ at local position $i \bmod 4$. The value of the whole number is

where $v_j = \sum_l b_{4j+l}2^l$ is exactly the 4-bit value of group $G_j$, and $16^j = (2^4)^j$. This is precisely the definition of $N$ written in base 16 with digits $v_j$. So grouping bits by 4 and converting each group independently is not an approximation or a shortcut with edge cases — it is a direct algebraic identity, which is why no carrying or borrowing across groups is ever needed.

Time complexity of repeated division. Converting a value $N$ to base $b$ via `ConvertToBase` performs one division per output digit, and a number $N$ has $\lceil \log_b(N+1) \rceil$ digits in base $b$. Each division/modulo step on fixed-width machine integers is $O(1)$ under the standard RAM model (or $O(\log N)$ bit-level cost if you insist on counting bit operations for arbitrary-precision integers). So the total work is

divisions, i.e., logarithmic in the value being converted, linear in the number of digits produced. This is optimal: you cannot emit fewer than $\Theta(\log_b N)$ symbols and still uniquely represent $N$, by a simple counting argument — $b^k$ distinct digit strings of length $k$ can represent at most $b^k$ distinct values, so representing values up to $N$ requires $k \ge \log_b(N+1)$.

Time complexity of binary–hex grouping. This algorithm makes a single linear pass over the bit string (or hex string), doing $O(1)$ table-lookup work per group/digit. With $n$ bits (equivalently $n/4$ hex digits), the cost is

again linear in the input/output length and asymptotically identical to repeated division — but with a much smaller constant factor and no actual arithmetic, since it is pure regrouping.

Space complexity. Both algorithms use $O(\log_b N)$ space to store the output digit string (and $O(1)$ auxiliary space beyond that, aside from the final reversal in `ConvertToBase`, which can be done in place).

Correctness argument for repeated division (invariant + induction). Claim: at the start of each loop iteration, the current value of `N` equals $\sum_{i} d_i b^{i - k}$ where $k$ is the number of digits already extracted and $d_i$ are the true base-$b$ digits of the original input. Base case: before any iterations, $k=0$ and the claim holds trivially (`N` is the original input). Inductive step: given the invariant holds with remaining value $N' = \sum_{i\ge k} d_i b^{i-k}$, we showed above that $N' \bmod b = d_k$ and $\lfloor N'/b \rfloor = \sum_{i \ge k+1} d_i b^{i-k-1}$, which is exactly the invariant with $k$ incremented by 1. The loop terminates because `N` strictly decreases (it is divided by $b \ge 2$ each time) and is a nonnegative integer, so it must reach 0 in finitely many ($\lceil\log_b(N+1)\rceil$) steps. On termination, every digit has been extracted in order $d_0, d_1, \dots, d_{n-1}$; reversing recovers the standard most-significant-first order. $\blacksquare$

Correctness argument for nibble grouping. This was already given algebraically above: splitting an $n$-bit string into 4-bit groups and reading each as a value $v_j \in [0,15]$ satisfies $N = \sum_j v_j \cdot 16^j$ by definition of positional notation in base 16, since $16 = 2^4$. No induction is even needed — it is a direct rewriting of one summation as a nested summation, exploiting that 4 divides evenly into the exponent structure. This is also precisely why grouping by 3 bits works for octal (base 8 = $2^3$), and why no such clean grouping exists for decimal, since $10$ is not a power of $2$.

Honest tradeoffs. Repeated division is universal — it works for converting to any base, including ones with no power-of-two relationship to binary (like decimal) — but it requires genuine arithmetic (division, modulo) at every step. Nibble grouping is essentially free computationally (bit shifts and masks in hardware, or table lookups by hand) but only works because $16$ is a power of $2$; you cannot use this shortcut to go directly from binary to decimal.

Convert $N = 46305$ (decimal) to binary and to hexadecimal, then cross-check the two answers against each other via nibble grouping.

Step 1 — decimal to binary via repeated division by 2:

Reading the bit column from bottom to top gives:

Step 2 — decimal to hexadecimal via repeated division by 16:

Reading bottom to top: $46305_{10} = \text{B4E1}_{16}$.

Step 3 — cross-check via nibble grouping (no arithmetic). Take the binary answer from Step 1 and split into 4-bit groups from the right: ``` 1011 0100 1110 0001 B 4 E 1 ``` This matches Step 2's independently-computed answer exactly, $\text{B4E1}_{16}$ — confirming both algorithms agree, as the correctness proofs guarantee they must, since they are two different routes computing the same base-16 representation of the same number.

Step 4 — verify by expansion.

The arithmetic closes the loop back to the original decimal value, confirming correctness end to end.

The binary numeral system predates electronic computing by centuries as a mathematical curiosity, but its marriage to physical hardware — and the parallel invention of compact notations like hexadecimal to manage it — is a distinctly 20th-century computer-architecture story.

Every layer of a real computing system leans on the binary/hex duality developed here. Machine instructions are stored as raw binary in memory, but assemblers, disassemblers, and debuggers print them in hex because a 32-bit instruction word is a readable 8-character hex string instead of an error-prone 32-character bit string. Memory addresses in a debugger (`0x7ffee23a1050`), color values in CSS and image formats (`#FF5733`), MAC addresses, cryptographic hash digests (SHA-256 output shown as 64 hex characters), and IPv6 addresses are all hex encodings of underlying binary data, chosen specifically because of the clean 4-bit-per-hex-digit correspondence proven above. Inside the CPU itself, every arithmetic and logic unit operates purely on bits — there is no hexadecimal circuitry anywhere in silicon. Understanding binary representation is the prerequisite for Logic Gates, which physically implement addition, comparison, and Boolean operations on those bit patterns. It is also the prerequisite for Two's Complement Integers, which extend unsigned binary to represent negative numbers using the same bit patterns reinterpreted, and for IEEE 754 Floating Point, which further subdivides a binary word into sign, exponent, and mantissa fields to represent real numbers. Compilers, linkers, and file-format specifications (ELF headers, PNG chunks, network packet headers) are routinely documented in hex precisely because it is the most legible lossless view onto the binary reality that hardware actually manipulates.

Ask the tutor: How does the same bit pattern get reinterpreted to represent negative numbers under two's complement?