Section 5.2 Binary representation
We typically write numbers in the base-\(10\text{,}\) or decimal, number system. Consider the number \(2,507\text{:}\)
When we write \(2,507\) we are saying the number is two thousands, five hundreds, and seven ones.
Decimal is convenient for humans, but we are required to remember how many of a particular power of ten is present. If you have done in programming, you know that computers are better suited to “if/else” statements: either a power is present or it is not. In that case, binary, or base-\(2\text{,}\) is convenient. Each digit is either \(1\) or \(0\) because a power of \(2\) will be present either exactly once or not at all.
Example 5.2.1.
Consider the binary number \((1011101)_2\text{.}\) The subscript \(2\) tells us this is a binary number and not, say, one million eleven thousand one hundred one. We can calculate the value of this number in decimal by expanding it as a sum of powers of \(2\text{:}\)
So, the number \((1011101)_2\) is the binary representation of the number \(93\text{.}\)
We will employ a recursive algorithm to write decimal numbers in binary form. Suppose we wish to write the integer \(N \ge 0\) as a binary number.
The binary expansion of \(0\) is \((0)_2\) and the binary expansion of \(1\) is \((1)_2\text{.}\) Otherwise...
Find the highest power \(2^{d-1}\) of \(2\) such that \(2^{d-1} \le N\text{.}\) We use this clunky notation so that our binary number has \(d\) digits.
The binary expansion of \(N\) is therefore \((1a_{d-2}a_{d-3}\ldots a_1a_0)\text{,}\) where the \(a_i\) are the remaining binary digits.
\((a_{d-2}a_{d-3}\ldots a_1a_0)\) is the binary expansion of \(N-2^{d-1}\text{,}\) possibly with some leading zeros.
The above algorithm is techical, but in practice it is easy. Find the highest power of \(2\) that is less than the number in question, and that tells you where to put your first (left-most) \(1\text{.}\) Then find the next highest power of \(2\) that is less than \(N-2^{d-1}\) and that will tell you where to put the next \(1\text{,}\) with \(0\)s in between.
Let's see a couple of examples. In order to write numbers in binary effectively, you will want to know the first few powers of \(2\) cold. They are:
\(2^0\) | \(2^1\) | \(2^2\) | \(2^3\) | \(2^4\) | \(2^5\) | \(2^6\) | \(2^7\) | \(2^8\) | \(2^9\) | \(2^{10}\) | \(2^{11}\) |
\(1\) | \(2\) | \(4\) | \(8\) | \(16\) | \(32\) | \(64\) | \(128\) | \(256\) | \(512\) | \(1024\) | \(2048\) |
Example 5.2.2.
To reverse the first example from this section, suppose we wanted to write \(93\) in binary. Let's start by finding the highest power of \(2\) that is less than or equal to \(93\text{.}\) In this case, that is \(2^{d-1} = 2^6 = 64\text{.}\) Because \(d-1=6\text{,}\) we know we will have \(7\) digits in our binary number. So far our number is
Next, we will find the highest power of \(2\) that is less than or equal to \(93-64=29\text{.}\) That is \(2^4=16\text{.}\) Our number so far is
Notice we set \(a_5=0\) because \(2^5=32\) does not appear in the expansion of \(93\text{.}\)
Next, we find the highest power of \(2\) that is at most \(29-16=13\text{.}\) It's \(2^3=8\text{.}\)
\(13-8=5\text{,}\) so \(2^2=4\) will fit.
\(5-4=1\text{,}\) so we will skip \(2^1=2\) and set \(a_0=1\text{.}\)
To make sure our reader knows that this is a binary number and not a long decimal number, we will wrap it in our binary notation: \((1011101)_2\text{.}\)
How is this recursive, you ask? Well, notice that \((11101)_2\) is the binary representation for the number \(29\text{,}\) which was \(93-64\text{.}\) Likewise, \((1101)_2\) is the binary representation for \(13\text{,}\) which was \(29-16\text{.}\) In other words, in order to find the binary representation for \(93\text{,}\) we find the binary representation for \(93-2^6\) and tack on the appropriate number of zeros. Here is the recursion.
Example 5.2.3.
Write \(2273\) in binary. (Try it yourself before reading on!)
Start by writing \(2273\) as a sum of powers of \(2\text{.}\) The highest is \(2^{11}=2048\text{,}\) so our number will have \(12\) digits. The full sum is
That means \(2273 = (100011100001)_2\text{.}\)
Though computer scientists are typically just concerned with base-\(2\) notation, our algorithm is not restricted to binary numbers. We can write numbers in any base using this process!
Example 5.2.4.
Write \(1143\) in base-\(5\) (quinary).
We need to know our powers of \(5\text{.}\) The necessary ones are \(1\text{,}\) \(5\text{,}\) \(25\text{,}\) \(125\text{,}\) and \(625\text{.}\) However, the nice thing about binary is that a power of \(2\) is either present or not. A power of \(5\) can be present up to \(4\) times (thereafter, it becomes the next power up). So the question is not only “is this power here?” but also “how many times?”
We may write:
so that the base-\(5\) expansion of \(1143\) is \((14033)_5\text{.}\)