An important issue in computing is our choice of representation for the objects that we wish to study. In particular, how to represent various types of numbers (natural numbers, rational numbers, real numbers) as well as other objects such as graphs. You are all familiar with the decimal (base 10) system for numbers. For example, to represent the positive integer three-hundred and twenty-four in its decimal form we would write “324”. This is shorthand for \(3 \times 10^2 + 2 \times 10^1 + 4 \times 10^0\). We know it is a decimal form because powers of \(10\) are used in the expression. You are probably so used to this representation that you don’t even think about it anymore. But let’s review the basic properties of decimal notation so that we set the standard for other representations that will be important.
When you read a number such as “324” in decimal, you see a sequence of decimal digits, \(d_{k-1} d_{k-2} \dots d_1 d_0\), where each digit \(d_i\) is in \(\{0, 1, 2, \dots, 9 \}\). The number that corresponds to this sequence of digits is \(\sum_{i=0}^{k-1} d_i \times 10^i\). In words, the right-most digit is multiplied by \(10^0\), the next digit to the left is multiplied by \(10^1\), and so on. Each digit to the left has a multiplier that is \(10\) times the multiplier of the previous digit. In our example “324”, we have \(d_2=3\), \(d_1=2\), and \(d_0=4\), and so the value is \(3 \times 10^2 + 2 \times 10^1 + 4 \times 10^0\).
Here are some useful properties of decimal representation:
To multiply a number by \(10\), you can just insert a \(0\) at the right end of its decimal form. That is, if a number \(n\) is represented by \(d_{k-1} d_{k-2} \dots d_1 d_0\), then the representation of \(10\times n\) is \(d_{k-1} d_{k-2} \dots d_1 d_0 0\). For example, \(10 \times 324\) is represented as 3240.
With the \(k\) decimal digit positions, exactly \(10^k\) unique numbers (from 0 to \(10^k-1\)) can be represented. For example, using three decimal digits (\(k=3\)), we can represent the numbers 0 through 999.
The binary (base 2) representation of a number uses the binary digits \(\{0, 1\}\) instead of the ten decimal digits \(\{0,1,2,\dots,9\}\). We write numbers in binary in the same sort of way that we write numbers in our traditional base 10 system. Again we represent a number by a sequence of binary digits, \(d_{k-1} d_{k-2} \dots d_1 d_0\), but now each digit \(d_i\) is 0 or 1. The value of the number corresponding to this sequence is: \(\sum_{i=0}^{k-1} d_i \times 2^i\). Note that the change in the expression is the change from powers of 10 to powers of 2. The number represented in its decimal form as 139 would represented in binary as: \(1 \times 2^7 + 1 \times 2^3 + 1 \times 2^1 + 1 \times 2^0 = 10001011\). In the sum, the terms multiplied by the digit \(0\) were omitted. The rightmost digit is multiplied by \(2^0=1\), the next to the left is multiplied by \(2^1=2\), and so on. Each digit to the left has a multiplier that is 2 times the previous digit. The above properties about decimal representation continue to hold, but now the 10’s are replaced by the new base, 2. Finally, we note that when discussing the binary representation of a number, the digits \(d_i\) are often called bits. Below are some examples of numbers together in their decimal and binary representation.
| Decimal | Binary |
|---|---|
| 1 | 1 |
| 2 | 10 |
| 3 | 11 |
| 4 | 100 |
| 5 | 101 |
| 6 | 110 |
| 7 | 111 |
| 8 | 1000 |
| 9 | 1001 |
| 10 | 1010 |
| 11 | 1011 |
| 12 | 1100 |
| 13 | 1101 |
| 14 | 1110 |
| 15 | 1111 |
| 16 | 10000 |
| 17 | 10001 |
| 18 | 10010 |
| 19 | 10011 |
| 20 | 10100 |
It is really easy to convert a number from its binary representation to its decimal representation. We express the number as a sum, expand out the powers in decimal, and add up using familiar decimal arithmetic. For example: \[100101 = 1 \times 2^5 + 0 \times 2^4 + 0 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 32 + 0 + 0 + 4 + 0 + 1 = 37.\] The binary expression \(100101\) and the decimal expression \(37\) are two ways for representing the same number.
Here is a process for converting from the decimal representation of a number to its binary representation. Consider the decimal number \(37\). We start by finding the largest power of \(2\) that is less than or equal to \(37\). In this case it is \(2^5\), since \(2^5=32\) and \(2^5 \le 37\), while \(2^6 = 64\) and \(2^6 \nleq 37.\) We can then write \(37 = 1 \times 2^5 + 5\). Now apply the same process with the unconverted remainder, the decimal number \(5\). The largest power of \(2\) that is less than or equal to \(5\) is \(2^2\), so we get \(5 = 2^2 + 1\). Continuing, the largest power of \(2\) that is less than or equal to \(1\) is \(2^0\). We get \(1 = 2^0 + 0\). With a remainder of \(0\), there is nothing left to convert. Now we collect everything together to get: \[37 = (1 \times 2^5) + (0 \times 2^4) + (0 \times 2^3) + (1 \times 2^2) + (0 \times 2^1) + (1 \times 2^0) = 100101\]