Expressing a value in an alternative number base.
Earlier in this document, we saw how we can use positional notation to compute the quantity expressed by representations in other number bases—but of course, we expressed the result of that computation in base-10. So now, let’s see how we can perform the reverse operation: expressing a quantity—which we almost certainly think of in base-10 terms at the start—using a radix other than 10. But as we do that, please observe that the algorithm presented here doesn’t depend at all on starting with a quantity expressed in base-10 terms, but only on the quantity itself, and on the radix of the representation we want to produce.
Caveats:
We’re going to restrict ourselves to integer quantities here, but the process can be extended to non-integers.
The algorithm below ignores issues of representation size, and follows the usual convention of using a leading minus sign (−) to indicate negative values.
Please note that the pseudocode below is not written in Java-like syntax; the only real similarity to Java is that any variable is declared by preceding the variable name with its type. It relies mostly on mathematical notation (though we’ve included detailed comments), with some additional symbols thrown in. Here are a few such symbols that might not be familiar to you, or that may be confusing because of the difference between their use here and their use in Java:
| Symbol | Description | Formal definition |
|---|---|---|
| $\mathbb{Z}$ | Set of all integers. | |
| $\mathbb{R}$ | Set of all real numbers. | |
| $\gets$ | Assignment operator (“gets”). | |
| $\lvert \hspace{0.1cm} \rvert$ | Absolute value. | \(\begin{alignedat}{2} && \lvert x \rvert & = \begin{cases} x, & \text{ if } x \ge 0; \\ -x, & \text{ if } x < 0; \end{cases} \\ & \text{where} \\ &&x & \in \mathbb{R}.\end{alignedat}\) |
| $\lfloor \hspace{0.1cm} \rfloor$ | Floor (rounding down) operator. | $\lfloor x \rfloor = \max(\lbrace n \in \mathbb{Z} \mid n \le x \rbrace).$ |
| $\bmod$ | Non-negative remainder. | \(\begin{alignedat}{2} & &a \bmod b &= a - \lfloor a / b \rfloor \cdot b, \\ & \text{where} \\ & & a &\in \mathbb{Z}, \\ && b &\in \lbrace c \in \mathbb{Z} \mid c > 0 \rbrace.\end{alignedat}\) |
| ε | Empty string or sequence. | $ε = \text{“” or } ().$ |
| $\frown$ | String (or other sequence) concatenation operator. | \(\begin{alignedat}{3}&\text{If} \\ & & C &= ( c_1, c_2, \ldots, c_m ), \\ & & D &= ( d_1, d_2, \ldots, d_n ), \\ & \text{then} \\ & & C^\frown D &= ( c_1, c_2, \ldots, c_m, d_1, d_2, \ldots, d_n ). \end{alignedat}\) |
| = | Equality comparison. | |
| ≠ | Inequality comparison. |
Input:
integer $m$.
($m$ is the value to be represented.)
integer $b$.
($b$ is the number base, or radix, here assumed to be greater than 1.)
character sequence $D = ( d_0, d_1, \ldots, d_{b-1} )$.
($D$ is an ordered sequence—array or list—of digit characters used in constructing the representation.)
To construct representation of $n$ using radix $b$:
integer $n \gets \lvert m \rvert$.
($n$ is a work variable, set initially to $\lvert m \rvert$.)
string $s \gets ε$.
($s$ is the representation being constructed, initially empty.)
While $n$ ≠ $0$:
(Repeat the indented steps below this, as long as $n$ is non-zero.)
integer $r \gets n \bmod b$.
($r$ is the non-negative remainder of the division $n / b$. )
$s \gets {d_r}^\frown s$.
(Prepend $d_r$, the digit character corresponding to $r$, to $s$.)
$n \gets \lfloor n / b \rfloor$.
(Divide $n$ by $b$, round down to get the quotient, and assign the result to $n$.)
If $s$ = $ε$, then
$s \gets d_0$.
(If $s$ is empty—i.e. no digits have been prepended to it—use the digit character corresponding to 0.)
otherwise, if $m < 0$, then
$s \gets$ ‘−’ $^\frown s$.
(If $m < 0$, prepend the minus sign to $s$.)
Return $s$.
Let’s use the algorithm above to construct the octal representation of 199:
Inputs
| Step | n | n ≠ 0 | s | r | s = ε | m < 0 | Return |
|---|---|---|---|---|---|---|---|
| 1 | 199 | ||||||
| 2 | ”” | ||||||
| 3 | true | ||||||
| 3.a | 7 | ||||||
| 3.b | “7” | ||||||
| 3.c | 24 | ||||||
| 3 | true | ||||||
| 3.a | 0 | ||||||
| 3.b | “07” | ||||||
| 3.c | 3 | ||||||
| 3 | true | ||||||
| 3.a | 3 | ||||||
| 3.b | “307” | ||||||
| 3.c | 0 | ||||||
| 3 | false | ||||||
| 4 | false | false | |||||
| 5 | “307” |
We can check our answer, using our understanding of positional notation:
\[\begin{aligned} 307_8 &= 7 \cdot 8^0 + 0 \cdot 8^1 + 3* 8^2 \\ &= 7 \cdot 1 + 3 \cdot 64 \\ &= 7 + 192 \\ &= 199 \end{aligned}\](We could also check our answer with JShell, by evaluating 0307.)
Let’s repeat the same example, using binary (base-2) this time.
Inputs
| Step | n | n ≠ 0 | s | r | s = ε | m < 0 | Return |
|---|---|---|---|---|---|---|---|
| 1 | 199 | ||||||
| 2 | ”” | ||||||
| 3 | true | ||||||
| 3.a | 1 | ||||||
| 3.b | “1” | ||||||
| 3.c | 99 | ||||||
| 3 | true | ||||||
| 3.a | 1 | ||||||
| 3.b | “11” | ||||||
| 3.c | 49 | ||||||
| 3 | true | ||||||
| 3.a | 1 | ||||||
| 3.b | “111” | ||||||
| 3.c | 24 | ||||||
| 3 | true | ||||||
| 3.a | 0 | ||||||
| 3.b | “0111” | ||||||
| 3.c | 12 | ||||||
| 3 | true | ||||||
| 3.a | 0 | ||||||
| 3.b | “00111” | ||||||
| 3.c | 6 | ||||||
| 3 | true | ||||||
| 3.a | 0 | ||||||
| 3.b | “000111” | ||||||
| 3.c | 3 | ||||||
| 3 | true | ||||||
| 3.a | 1 | ||||||
| 3.b | “1000111” | ||||||
| 3.c | 1 | ||||||
| 3 | true | ||||||
| 3.a | 1 | ||||||
| 3.b | “11000111” | ||||||
| 3.c | 0 | ||||||
| 3 | false | ||||||
| 4 | false | false | |||||
| 5 | “11000111” |
(This time, we’ll leave it to you to check the answer.)
In the previous example, we saw that $199_{10} = 307_8 = 11000111_2$. Since $8 = 2^3$, maybe we can take advantage of that to ease moving from a base-2 representation to a base-8 one, or vice versa.
Let’s try breaking up the base-2 representation in groups of 3 digits. Keep the digits in the same order—but starting from the right, put a space between each group of 3: \(\begin{matrix} 11_2 & 000_2 & 111_2 \end{matrix}\)
For consistency, let’s left-pad the left-most group with an extra zero, so that it has 3 digits: \(\begin{matrix} 011_2 & 000_2 & 111_2 \end{matrix}\)
We know that in a binary representation, $N$ binary digits (bits) are capable of representing $2^N$ distinct values. So each group of 3 bits is capable of representing 8 values. What happens if we take the value of each group, and represent it as an octal digit, writing each of those underneath the corresponding group? \(\begin{matrix} 011_2 & 000_2 & 111_2 \\ \hline 3_8 & 0_8 & 7_8 \end{matrix}\)
If we push those octal digits back together, we get $307_8$. By taking the octal representation of each group of 3 binary digits in order, we ended up with the octal representation of the entire number! It shouldn’t take much work to verify that we can also go in the opposite direction—that is, start with the octal representation, and convert each digit to its 3-bit binary representation, to arrive at the base-2 representation of the entire number.
Does the same thing work for hexadecimal? Let’s check, by taking the base-2 representation of our example, and dividing it into groups of 4 digits ($16 = 2^4$): \(\begin{matrix} 1100_2 & 0111_2 \end{matrix}\)
To help us keep things straight, let’s next write the base-10 representations of each digit group underneath: \(\begin{matrix} 1100_2 & 0111_2 \\ \hline 12_{10} & 7_{10} \end{matrix}\)
Finally, remembering that in hexadecimal we use the letters A–F to represent the values 10–15 (in that order), we can write the corresponding hexadecimal digits underneath each digit group: \(\begin{matrix} 1100_2 & 0111_2 \\ \hline 12_{10} & 7_{10} \\ \hline \text{C}_{16} & 7_{16} \end{matrix}\)
If our experience holds, $\text{C7}_{16}$ should be equal to $199_{10}$ (and $307_8$ and $11000111_2$). And in fact, a simple check will show that $12 \cdot 16^1 + 7 \cdot 16^0 = 199$. (Again, we can also use JShell to evaluate 0xC7.)