Discrete Mathematics for Computing (Draft)

Let’s shift away from our standard base-10 number system (commonly referred to as the decimal system), and think about representing values in other bases. The discussion about place-value in the previous section gives us all of the tools we need.

Given a base \(b\) (with \(b > 0\)) and digits \(a_k, a_{k-1}, \cdots, a_1, a_0\) with \(0 \leq a_i \lt b\text{,}\) the number \(\left(a_{k}a_{k-1}\cdots a_{1}a_{0}\right)_b\) represents the value \(a_{k}b^{k} + a_{k-1}b^{k-1} + \cdots + a_{1}b^{1} + a_{0}b^{0}\text{.}\) For example, the number \(\left(2501\right)_{6}\) is the value \(2\cdot \left(6^3\right) + 5\cdot \left(6^2\right) + 0\cdot \left(6^1\right) + 1\cdot \left(6^0\right)\text{.}\)

The definition above gives us a simple method for converting numbers represented in any non-standard base into their decimal representations. We need only write out their expansions in the provided base, and then simplifly using our familiar operations. For example, the decimal representation of \(\left(2501\right)_{6}\) is \(613\text{.}\) You can verify this from the expansion in the previous paragraph. Let’s try some examples below.

Beyond our own base-10 (decimal) number system, there are others that are quite common. In particular, base-2 (binary), base-8 (octal), and base-16 (hexadecimal) are popular. Let’s explore those number systems a bit further.

In the previous subsection, we identified how number systems in different bases work, and highlighted how it is just a generalization of representing numbers using our common decimal system. From that discussion, we see that the binary system utilizes only two digits, 0 and 1, and place-values are attached to increasing powers of 2 as we move towards the left. These binary digits are often referred to as bits. Moving to the octal system, we can deduce that it utilizes eight digits, 0 through 7, and that place-values are determined by increasing powers of 8 as we move towards the left.

The understanding above extends to hexadecimal, but creates a small problem. We’ve run out of digits to use. Indeed, the hexadecimal system will utilize sixteen unique digits. To accommodate this, we’ll utilize 0 through 9 as usual, but then include \(A\) through \(F\) to represent the quantites 10 - 15, as we know them. Why can’t we use 10 - 15 to represent themselves? If we did so, the encoding \(\left(510\right)_{16}\) becomes ambiguous. For example, do we mean \(\left(5\cdot 16^2 + 1 \cdot 16^1 + 0\cdot 16^0\right) = \left(1296\right)_{10}\) or do we mean \(\left(5\cdot 16^1 + 10\cdot 16^0\right) = \left(90\right)_{10}\text{?}\) Making use of the characters \(A\) through \(F\) prevents this ambiguity. The correct hexadecimal encoding of \(90_{10}\) would be \(\left(5A\right)_{16}\text{.}\) We’ll discuss more on how to make this conversion in the next section.

In this section we’ve seen that numbers can be written in a variety of bases. In particular, any positive integer can serve as the base for a number system. For bases larger than 10, we run out of our (familiar) digits, and need to include symbols to represent larger quanitities -- like using the characters \(A\) through \(F\) to represent 10 - 15 in the hexadecimal system.

In order to understand quantities written in different bases, we often need to convert them back to the decimal system (base-10). This is because we don’t commonly work in those non-standard base-systems and have little intuition for them. We can exploit what we know about *place-value* in converting from a known non-standard base \(b\) into the corresponding decimal value. The equation below describes the conversion.

There are several non-standard bases which are commonly utilized in computing. In particular, it is not surprising to encounter the binary, octal, or hexadecimal systems. Binary is commonly encountered because computers think in terms of the presence or absence of an electrical signal. Recognizing that there are only two observable states shows why we are limited to two digits. Binary encodings can be quite long and cumbersome, grouping bits together can reduce the "length" of an encoding. For example, grouping every three consecutive bits together results in an octal encoding whole grouping every four consecutive bits together results in a hexadecimal encoding. It is very fast to switch between any of these three number systems because of this relationship.