Number Systems and Base Conversion

A number system of radix (base) $r$ represents each value as a weighted sum of powers of $r$, with digit symbols drawn from $\{0, 1, \ldots, r-1\}$. Digital hardware uses radix 2 because two voltage levels are reliable; humans prefer radix 10; programmers also use radix 8 (octal) and radix 16 (hexadecimal) as compact notations for binary bit patterns.

This topic covers conversions between bases, the bit width needed for a given range, and the binary expansion of fractions. Signed encodings and IEEE floating point build on these facts; they are treated in separate notes.

An $n$-digit integer in radix $r$

has decimal value

A fractional part $(0.d_{-1}d_{-2}\ldots d_{-m})_r$ contributes $\sum_{k=1}^{m} d_{-k}\, r^{-k}$.

Hexadecimal digits. A $= 10$, B $= 11$, C $= 12$, D $= 13$, E $= 14$, F $= 15$. Case does not matter for the value.

Valid-digit rule. A numeral is legal in radix $r$ only if every digit is less than $r$. So the smallest radix in which a numeral can be read is $\max(2,1+\text{largest digit})$: $(2071)_r$ needs $r \ge 8$, and a numeral containing the digit 9 can never be octal. Every unknown-radix question starts by writing down this lower bound.

Range of $n$ digits in radix $r$. The $n$-digit numerals in radix $r$ are exactly $0$ to $r^n - 1$, so there are $r^n$ of them. If leading zeros are forbidden, there are $(r-1)\,r^{n-1}$ numerals with exactly $n$ digits; for example, $6 \cdot 7^2 = 294$ three-digit numerals in base 7.

Because $2^3 = 8$ and $2^4 = 16$, every three bits map to one octal digit and every four bits map to one hex digit, with no leftover. That is why octal and hex are lossless shorthands for binary, while decimal is not.

Useful powers of two:

With $n$ bits you can represent exactly $2^n$ distinct patterns, namely the integers $0, 1, \ldots, 2^n - 1$. To represent $N$ distinct values you need at least $\lceil \lg N \rceil$ bits. For $N = 1000$, $\lceil \lg 1000 \rceil = 10$ because $2^9 = 512 < 1000 \le 1024 = 2^{10}$.

Expand by powers. Example: $(234)_8 = 2\cdot 8^2 + 3\cdot 8^1 + 4\cdot 8^0 = 128 + 24 + 4 = 156_{10}$. Same method for any radix.

Repeatedly divide by $r$ and record remainders. They are generated least significant first; read bottom to top to obtain digits most significant to least significant.

Example. Convert $156_{10}$ to binary:

Reading remainders bottom to top: $156_{10} = (10011100)_2$. The same procedure with divisor 8 gives $(234)_8$; with divisor 16 gives $(9\text{C})_{16}$.

If both radices are powers of a common base, grouping applies. When one radix is a power of the other, $R = r^k$, group $k$ radix-$r$ digits per radix-$R$ digit, exactly as for binary and hex. When they share a common base but neither is a power of the other, as with octal and hex ($8^4 = 16^3$), group through that base, or map 4 octal digits directly to 3 hex digits. Otherwise go through decimal.

Example. $(2120)_3$ to base 9: since $9 = 3^2$, group pairs from the right: $21 \mid 20$. Then $(21)_3 = 7$ and $(20)_3 = 6$, so $(2120)_3 = (76)_9$. Check: $2\cdot 27 + 1\cdot 9 + 2\cdot 3 + 0 = 69$ and $7\cdot 9 + 6 = 69$.

Example. $(725)_8$ to hex: octal digits to bits $111\,010\,101$, regroup in fours from the right $0001\,1101\,0101$, so $(725)_8 = (1\text{D}5)_{16} = 469_{10}$.

Example. $(7255)_8$ to hex by mapping 4 octal digits to 3 hex digits, because $8^4 = 16^3$: $7255_8 = 111\,010\,101\,101_2 = 1110\,1010\,1101_2 = (\text{EAD})_{16} = 3757_{10}$.

Multiply the fractional part by 2; the integer part of the product is the next bit; repeat on the new fractional part. Stop when the fraction becomes 0 or when enough bits are obtained.

Example. $0.625_{10}$: $0.625\times 2 = 1.25$ (bit 1), $0.25\times 2 = 0.5$ (bit 0), $0.5\times 2 = 1.0$ (bit 1). So $0.625_{10} = 0.101_2$.

Recurring fractions. Many finite decimals are infinite in binary. The fraction $0.1_{10}$ yields the repeating bit string $0.0001100110011\ldots_2$. The first eight bits after the point are $00011001$. Hardware therefore stores an approximation. For inexact computations where approximate agreement is intended, use suitable absolute/relative tolerances; exact equality is appropriate when the specification requires it (see Floating-Point Representation).

Sum bit weights: $0.101_2 = 1\cdot 2^{-1} + 0\cdot 2^{-2} + 1\cdot 2^{-3} = 0.5 + 0.125 = 0.625_{10}$.

Addition works column by column as in decimal: when a column sum $s$ reaches $r$ or more, write $s - r$ and carry 1 (a column sum can never exceed $2r - 1$, so the carry is at most 1).

For an $n$-digit number $N$ in radix $r$:

Examples: the 9's complement of $546700$ is $453299$ and its 10's complement is $453300$. The 1's complement of $1011000$ is $0100111$ and its 2's complement is $0101000$.

Subtraction by complement addition. To compute $M-N$ with $n$ radix-$r$ digits, first return $M$ if $N=0$. Otherwise add $M$ to the r's complement of $N$, retaining the end carry. An end carry means a nonnegative result, including zero when $M=N$; discard only that final carry.

Decimal, 5 digits: $61428 - 02375$. The 10's complement of $02375$ is $97625$, and $61428 + 97625 = 159053$. Discard the carry: $59053$. Reversed, $02375 - 61428$: $02375 + 38572 = 40947$, no end carry, so the answer is $-(10\text{'s complement of } 40947) = -59053$.

The same rule in binary with the 2's complement is the basis of every hardware subtractor (see Signed Number Representation). With the (r-1)'s complement instead, an end carry is not discarded but added back to the least significant digit (end-around carry).

Pseudocode uses integer division div and remainder mod, and writes digits into an array from the least significant position.

Cost and storage model. Count unit-cost exact-register arithmetic, comparisons and amortised constant-time output append; these are digit/iteration counts, not arbitrary-precision bit costs. Let $d=1$ for $N=0$, otherwise $d=\lfloor\log_r N\rfloor+1$. DEC-TO-RADIX takes $\Theta(d)$ operations in every case at a fixed digit length, including in-place reversal, and uses $\Theta(d)$ output-materialization storage plus $O(1)$ registers beyond those buffers. If converting the digit list allocates a separate final string, the temporary list itself is $\Theta(d)$ auxiliary storage when only the returned string is excluded; constant workspace is claimed only when the digit buffer is also excluded or reused as output. For FRAC-DEC-TO-BIN let $t$ be the actual iterations with a nonnegative integer cap. Time is $\Theta(t+1)$ and output storage $\Theta(t+1)$ including the empty-list header, with $O(1)$ working registers excluding that returned list and the input. These storage bounds apply in best, average and worst cases through their respective output lengths; exact-register counts do not imply constant bit storage for unbounded numbers.

Uniqueness. For integer radix $r \ge 2$, every non-negative integer has a unique finite representation with no leading zeros (the single digit 0 represents zero). Fractions need not terminate; a terminating expansion in one radix need not terminate in another.

Digit count. The number of digits of $N \ge 1$ in radix $r$ is $\lfloor \log_r N \rfloor + 1 = \lceil \log_r (N+1) \rceil$ for the usual floor form, equivalently one more than the exponent of the highest power of $r$ not exceeding $N$.

Bit width for a range. To store every integer in $\{0, 1, \ldots, M\}$ you need $\lceil \lg (M+1) \rceil$ bits. To store $N$ distinct codes you need $\lceil \lg N \rceil$ bits.

Unknown-radix equations. Expand every numeral as a polynomial in the unknown radix, solve, and keep only integer roots that exceed the largest digit present. Three outcomes occur and all three are examinable:

When does a fraction terminate? Write the fraction in lowest terms $p/q$. Its radix-$r$ expansion terminates if and only if every prime factor of $q$ divides $r$. Proof sketch: a terminating expansion with $k$ digits is $m / r^k$, which forces $q \mid r^k$; conversely if every prime of $q$ divides $r$, then $q \mid r^k$ for large enough $k$ and $p/q = (p\,r^k/q)/r^k$.

Digit count of large powers. $2^{100}$ has $\lfloor 100 \log_{10} 2 \rfloor + 1 = 31$ decimal digits, but in hex it is a 1 followed by 25 zeros (since $2^{100} = 16^{25}$), so it has 26 hex digits. In octal, $2^{100} = 2 \cdot 8^{33}$, which is 34 octal digits.

$(\text{BEEF})_{16} = 11\cdot 16^3 + 14\cdot 16^2 + 14\cdot 16 + 15 = 48879_{10}$. Expanding digits: B $= 1011$, E $= 1110$, E $= 1110$, F $= 1111$, so $\text{BEEF}_{16} = 1011\,1110\,1110\,1111_2$.

$(475)_8 = 4\cdot 64 + 7\cdot 8 + 5 = 317_{10}$. Binary grouping of $475_8$: $100\,111\,101_2$.

$\lceil \lg 1000 \rceil = 10$. With 10 bits the range is $0..1023$, which covers 1000 values; 9 bits cover only 512 values.

Repeated multiplication of $0.1$ by 2 for eight steps yields bits $0,0,0,1,1,0,0,1$. Truncating to eight fractional bits stores $0.00011001_2 = 25/256 = 0.09765625_{10}$, an absolute error of about $0.00234$.

How many 1 bits does the binary form of $3 \cdot 4096 + 15 \cdot 256 + 5 \cdot 16 + 3$ have? Because $4096 = 16^3$, $256 = 16^2$ and $16 = 16^1$, the coefficients are hex digits: the number is $(3\text{F}53)_{16} = 0011\,1111\,0101\,0011_2$. Count per digit: $2 + 4 + 2 + 2 = 10$ ones. The value is $16211_{10}$, but no decimal conversion is needed. Imperative rule. When a sum is written in powers of 8 or 16, read it directly as octal or hex digits, provided each coefficient is a legal digit.

Find $b$ with $(123)_b = 38_{10}$. Then $b^2 + 2b + 3 = 38$, $b^2 + 2b - 35 = (b + 7)(b - 5) = 0$, so $b = 5$, which exceeds the largest digit 3. A second check: in base 5, $(123)_5 = 25 + 10 + 3 = 38$.

Common misconceptions.