Base 2 Arithmetics

Why is it that so many things in computing seem to be organized into fours, eights, and sixteens? What is the difference between Ethernet and Internet? In spite of efforts to make networks and the Internet transparent to users, there remain many places where a little bit of understanding of electronics and binary arithmetic can help you make some sense of what is happening.

At the base of the network you use is the physical layer. This is the actual cable, network interface cards, and other hardware that is required to make the network function. There are many different styles of cable used on computer networks, and different kinds of communication used on those cables, but many of them rely on sending low-voltage electrical signals over the cables. Those voltages are always interpreted in a binary sense - either on or off. If a voltage is "on", then it is interpreted as a one, while if the voltage is "off", then it is interpreted as a zero. Of course, there are network media that use light instead of electrical signals to record those "on" and "off" notions, but logically, the idea is the same.

Since every signal is composed fundamentally of ones and zeros, then mathematically we are working in base two. For anyone familiar with number systems, this should present no problem, but let's review it here. When we write a base two numeral, the only digits permissible are ones and zeros. As in a decimal representation of numbers, the position of the digits has a meaning in terms of the power of the base that the digit is multiplied by. More simply, in this case the rightmost digit multiplies \(2^0\), the second digit from the right multiplies \(2^1\), the third from the right multiplies \(2^2\), and so on. When there is ambiguity it is convenient to write the base of the number being expressed using a subscript. For example we can write \(10_2=2_{10}\). This cryptic expression indicates that \(10_2 = 1\times2^1+0\times2^0=2\), with the last number written in base ten. Example [ExampleBinary] gives more instances of this.

Example: [ExampleBinary] \begin{align*} 100_2 &= 1\times2^2+0\times2^1+0\times2^0 = 4_{10}\\ 101_2 &= 1\times2^2+0\times2^1+1\times2^0 = 5_{10}\\ 111_2 &= 1\times2^2+1\times2^1+1\times2^0 = 7_{10}\\ 1001_2 &= 1\times2^3 +0\times2^2+0\times2^1+1\times2^0 = 9_{10}\\ 10011001_2 &= 1\times2^7 + 0\times2^6 + 0\times2^5 +1\times2^4\\ &\qquad +1\times2^3 +0\times2^2+0\times2^1+1\times2^0\\ &=153_{10}. \end{align*}

In computing, each digit of the binary representation is called a bit. These bits are typically organized further into groups of eight, called either bytes when we are discussing the size of files, or in the context of networking, octets. We typically do not want to write eight binary digits for every number we discuss, but eight binary digits are sufficient to represent numbers from 0 to 255, inclusive, such numbers appear prominently in all aspects of computation. There are several ways to write these numbers. Obviously we can use a decimal representation as we have above, but it is equally common in computing to use a hexadecimal representation.

Hexadecimal means: "base sixteen". Writing hexadecimal numbers is requires more digits - we need single digits to represent ten through fifteen. It is traditional to use the letters A through F for this purpose. In other words, if we were to count in hexadecimal, it would go like this: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, 10, 11,... This all fits together nicely with base two: \(16 = 2^4\). Thus, any hexadecimal digit may be represented as a four digit binary number (four bits), and conversely, four bits may be represented by a single hexadecimal digit. Moreover, \(256 = 16^2\), so that we may use one hexadecimal number to represent the upper four bits of an octet, and a second hexadecimal number to represent the lower four bits. Thus, any number from 0 to 255 inclusive can be represented by a two-digit hexadecimal number. The position of the digit again signifies the the power of sixteen by which it is to be multiplied. Example [ExampleHex] illustrates this further.

Example: [ExampleHex] \begin{align*} 10000000_2 &= 128_{10} = 80_{16};\\ 10011001_2 &= 153_{10} = 99_{16};\\ 11110001_2 &= 241_{10} = F1_{16};\\ 11010_2 &= 26_{10} = 1A_{16}. \end{align*}
It is easy to convert between binary and hex. The rightmost four binary digits represent numbers from 0 to 15 (in base 10), and the fifth digit from the right is in the sixteens place. In other words, the second set of four digits from the right represent the number of sixteens in the number. Likewise, the third set of four digits from the right give the number of \(16^2\)s in the binary number. Thus, given any binary number, we only have to group its digits into fours, and then write the hex representation for each of those groups. For instance, in Example [ExampleHex] the third line shows that \(11110001_2 = F1_{16}\). Observe that the first four digits of \(11110001_2\) are \(1111 = F_{16}\). The second four digits are \(0001 = 1_{16}\). Grouping the digits into fours allows us to write down the hex representation immediately. Again, in the last line of Example [ExampleHex] we see that \(11010_2= 1A_{16}\). This time the binary number is not divided evenly by fours, so we pad it on the left using zeroes: we write \(00011010_2=11010_2\). Written that way, we break it into fours: \(0001_2=1_{16}\) and \(1010_2=A_{16}\).

Converting from hex to binary is just as easy. Each hex digit can be written as four binary digits, and place holding is preserved. For example, suppose we want to write the binary representation for \(B3_{16}\). We know that \(B_{16}=1011_2\), and \(3_{16}=0011_2\), so that \(B3_{16}=10110011_2\). Again, \(3B_{16}=0011\,1011_2=111011_2\).

We have seen that it is not very hard to convert from hex to decimal (base ten): we just expand the expression gigit by digit as we described above. For example, we can write \(B3_{16}=B\times16^1+3\times16^0=11\times16+3\times1=179_{10}\). In the same way \(3B_{16}=3\times16+11\times1=59_{10}\). By contrast, converting from decimal to binary or hex is not all that easy. To convert a number from decimal to hex, we first have to know how many hex digits will be required. Observe that \(179_{10}\) has a three-digit decimal representation, but only a two-digit hex representation, so we see that there is an issue here.

Since each hex digit of a representation is a coefficient of 16 to some power, it follows that finding out how many hex digits are required to represent a given decimal number amounts to finding the largest power of 16 that is less than or equal to that number. For our example we see that \(16^0=1\le179, 16^1=16\le179\), but \(16^2=256 > 179\). Thus the hex representation of 179 will have \(16^0\) and (16^1\) terms, but no \(16^2\) term, so we need only two hex digits.

Next, we have to figure out what the coefficients of those terms are. We start with the highest degree terms: for our current example \(16^1\). How many \(16^1\)s are there in \(179\)? The answer is \(11\), because \(11\times16^1=176\le179\). Thus the first digit in the hex representation is eleven -- \(B\) in hex. For the the rest of the digits, we subtract the part we have accounted for so far from the original number: \(179-11\times16^1 = 3\). Thus, our hex representation for \(179\) is \(B3_{16}\). Another illustration of this can be seen in Example [ExampleDecimalConvert].

Example: [ExampleDecimalConvert] Convert \(312_{10}\) to hex and binary.

We note that (16^0=1\le312; 16^1=16\le312; 16^2=256\le312;\), but \(16^3=4096>312\), so our hex conversion will have coefficients for the \(16^0, 16^1,\) and \(16^2\) terms: three digits.
How many \(16^2\)s are there in \(312\)? There is just one, so the first digit is 1. That accounts for \(256\) of the \(312\); we still need digits to account for \(312-256 = 56\).
How many \(16^1\)s are there in \(56\)? There are three: \(3\times16=48\). Now there are only \(56-48=8\) unaccounted for. The last digit is \(8\).
We conclude that \(312_{10}=138_{16}\). To convert to binary, just write each hex digit as four bits: \(138_{16}=0001\,0011\,1000_2=100111000_2\).

Hexadecimal numbers - hex, for short - appear often in computing as a way to shorten the notation and ease the computations for binary numbers. For example, hexadecimal numbers are typically used in writing addresses for Ethernet networks, as we see in the next section.