7.3: Hexadecimal (base 16)

Now objectively speaking, it turns out that ten is a pretty weird base too. I know it doesn’t seem like it, but that’s only because we’re so used to it. Really, if you’re repeatedly adding little circles to a drawing, ten is a funny place to decide to draw the line and go to more digits. It’s only divisible by 2 and 5 (of all things), it’s not a perfect square, and all this makes it kind of an awkward choice.

In computer science, it turns out to be very (very) convenient to use a base that is a power of two. This means a base that is “two-to-the-something." In earlier computing days, octal (base 8) was a common choice. But for various reasons, that turns out to be less convenient than using base 16, or hexadecimal.¹ Any time you’re working with hardware, operating systems, device drivers, bit masks, or anything else low level, you’ll encounter numbers written in base 16 a heck of a lot. So let’s study this particular base in some detail.

Base 16 will need sixteen digits, of course. Unfortunately, we ten-fingered people have only invented ten symbols that are obviously numerical: the digits 0 through 9. So what do we do for the other six? It turns out that the originators of this system took perhaps the most obvious approach: repurposing the letters of the alphabet. So we add the “digits" A through F (sometimes written as capitals, sometimes in lower-case) to our set of symbols. These, then, are the quantities that each individual digit represents:

0	zero
1	one
2	two
3	three
4	four
5	five
6	six
7	seven
8	eight
9	nine
A	ten
B	eleven
C	twelve
D	thirteen
E	fourteen
F	fifteen

The inventors of hexadecimal notation didn’t have to use the alphabet, of course; they could have chosen a star for ten, a square for eleven, a happy face for twelve, etc., but that wouldn’t have been very easy to type. So we’re stuck with the letters, for better or for worse. Practice staring at that letter A and saying the word “ten." Because that’s what it means. In hexadecimal, the sequence of digits 10 does not mean “ten." It means “sixteen."

Those are the symbols. What are the place values? Well, they are (from the right) the \(16^0\)’s place, the \(16^1\)’s place, the \(16^2\)’s place, and so on. Written decimally, those work out to be the 1’s place, the 16’s place, the 256’s place, the 4096’s place, and so on. Again, those numbers seem strange only because when they are written decimally they don’t come out very “round."

The value of a number like 72E3 is computed as: \[\text{72E3}_{16} = 7 \times \text{4096}_{10} + 2 \times 256_{10} + 14 \times 16_{10} + 3 \times 1_{10} = \text{29,411}_{10}.\] Notice we treated the “E" just like another digit, which it is. We also called 72E3 “a number," which it is. Get used to the idea that numbers — totally legitimate numbers — can have letters for some of their digits.

In hexadecimal, what’s the highest value that can fit in one digit? Answer: F (which is fifteen.) What’s the highest that can fit in two digits? FF (which is two hundred fifty-five.) What about three digits? FFF (which is sixty-five thousand five hundred thirty-five.) And so on. If you count in hexadecimal, you do the same thing as in decimal, only you “roll over the odometer" when you get to F, not when you get to 9.

Converting to and from decimal

So we know how to take a hexadecimal number (like \(\text{72E3}_{16}\)) and find its decimal equivalent: we just interpret each place’s value as 1, 16, 256, 4096, and so on. What about going the other way? If we had a decimal number, how would we write its value hexadecimally?

First, let’s learn two operations (if you don’t already know them) that come in handy when working with integers. The first is called the modulo operator (written “mod"), and simply gives the remainder when dividing two numbers. This is a concept you probably learned in elementary school but might not have used since then. As we get older (and use calculators), we tend to think of a division operation like \(13 \div 3\) as being \(4.333\dots\). But that’s when we want a real-valued (instead of integer-valued) answer. If we only want integers, then we say that \(13 \div 3\) is “4 with a remainder of 1." (The “4" is called the quotient.) This means that if you have 13 objects, you can take four groups of 3’s out of them, and then have 1 object left over. The way we write this operation mathematically is “13 mod 3." In this case, it turns out that 13 mod 3 = 1.

Let’s think through what the mod operator yields for different values. We know that 13 mod 3 = 1. What about 14 mod 3? That is equal to 2, since we can (again) take out four groups of 3’s, but then we’d have two left over. What about 15 mod 3? That yields 0, since 3 goes in to 15 evenly, leaving no remainder at all. 16 mod 3 again gives us 1, just like 13 did. If you think it through, you’ll realize that 19 mod 3 will also be 1, as will 22 mod 3 and 25 mod 3. These numbers that give the same remainder are said to be “congruent mod 3." The numbers 2, 5, 8, 11, 14, etc. are also all congruent (to each other) mod 3, since they all give a remainder of 2.

Another observation is that the value of \(n\) mod \(k\) always gives a value between 0 and \(k-1\). We may not know at a glance what 407,332,117 mod 3 is, but we know it can’t be 12, or 4, or even 3, because if we had that many elements left after taking out groups of 3’s, we could still take out another group of 3. The remainder only gives us what’s left after taking out groups, so by definition there cannot be an entire group (or more) left in the remainder.

The other operation we need is simply a “round down" operation, traditionally called “floor" and written with brackets: “\(\lfloor \ \rfloor\)". The floor of an integer is itself. The floor of a non-integer is the integer just below it. So \(\lfloor 7 \rfloor = 7\) and \(\lfloor 4.81 \rfloor = 4\). It’s that simple.

The reason we use the floor operator is just to get the whole number of times one number goes into another. \(\lfloor 13 \div 3 \rfloor = 4\), for example. By using mod and floor, we get the quotient and remainder of a division, both integers. If our numbers are 25 and 7, we have \(\lfloor 25 \div 7 \rfloor = 3\) and 25 mod 7 = 4. Notice that this is equivalent to saying that \(25 = 3 \times 7 + 4\). We’re asking “how many groups of 7 are in 25?" and the answer is that 25 is equal to 3 groups of 7, plus 4 extra.

The general procedure for converting from one base to another is to repeatedly use mod and floor to strip out the digits from right to left. Here’s how you do it:

Express a numeric value in a base

1. Take the number mod the base. Write that digit down.

2. Divide the number by the base and take the floor:

   1. If you get zero, you’re done.

   2. If you get non-zero, then make this non-zero number your new value, move your pencil to the left of the digit(s) you’ve already written down, and return to step 1.

As an example, let’s go backwards to the hex number 72E3 as in our example above, which we already computed was equal to 29,411 in decimal. Starting with 29,411, then, we follow our algorithm:

1. (Step 1) We first compute 29,411 mod 16. This turns out to be 3. Many scientific calculators can perform this operation, as can programming languages like Java and data analysis languages like R. Or, you could do long division (459,494 \(\div\) 16) by hand and see what the remainder is. Or, you could divide on an ordinary calculator and see whether the part after the decimal point is 0, or \(\frac{1}{16}^\text{th}\), or \(\frac{2}{16}^\text{ths}\), etc. Or, you could sit there and subtract 16 after 16 after 16 from 29,411 until there are no more 16’s to take out, and see what the answer is. At any rate, the answer is 3. So we write down 3:

   3

2. (Step 2) We now divide 29,411 by 16 and take the floor. This produces \(\lfloor \text{29,411} \div 16 \rfloor = 1838\). Since this is not zero, we perform step 1: make 1838 our new value, move our pencil to the left of the 3, and go back to step 1.

3. (Step 1) Now compute 1838 mod 16. This gives us the value 14, which is of course a base 10 number. The equivalent hex digit is E. So we now write down E to the left of the 3:

   E3

4. (Step 2) Dividing 1838 by 16 and taking the floor gives us 114. Since this is again not zero, we perform step 2.2: make 114 our new value, move our pencil to the left of the E, and go back to step 1.

5. (Step 1) Next we compute 114 mod 16. This turns out to be 2, so we write down a 2:

   2E3

6. (Step 2) Computing \(\lfloor 114 \div 16 \rfloor\) produces 7, which is again not zero, so 7 becomes our new value and we go back once again to step 2.2.

7. (Step 1) 7 mod 16 is simply 7, so we write it down:

   72E3

8. (Step 2) Finally, \(\lfloor 7 \div 16 \rfloor\) is zero, so we go to step 2.1 and we’re done. The page has 72E3 written on it in big bold letters, which is the correct answer.

Adding hex numbers

Suppose we have two hexadecimal numbers, and we want to add them together to get a hexadecimal result. How do we do it? One way is to first convert them both to decimal, then add them like you learned in first grade, then convert the answer back to hex. But we can stay “natively hex" as long as we add each pair of digits correctly.

Let’s try it. Suppose we want to compute this sum: \[\begin{array}{*{5}{c@{\hspace{0pt}}}} & 4 & 8 & \text{D} & 4_{16} \\ + & 5 & 9 & 2 & 5_{16} \\ \hline & & & & ?_{16} \\ \end{array}\] We proceed in the first-grade way from right to left. Adding the one’s-place values, we get 4 + 5 = 9: \[\begin{array}{*{5}{c@{\hspace{0pt}}}} & 4 & 8 & \text{D} & 4_{16} \\ + & 5 & 9 & 2 & 5_{16} \\ \hline & & & & 9_{16} \\ \end{array}\] Easy enough. Now we add the next digit to the left (the sixteen’s-place, mind you, not the ten’s place) and we find D + 2. Now what in the world is “D+2"? It’s actually easy: all you have to do is the same thing you did when you were a child and you had to add something like 4 + 5. You hadn’t memorized the answer yet, and so you started with four fingers held up, and counted off “1…2…3…4…5," sticking up another finger each time. Then, you looked at your hands, and behold! nine fingers.

We’ll do the same thing here: start with the number “D," and count two additional places: “E…F." The answer is F. That is the number that’s two greater than D. Lucky for us, it still fits in one digit. So now we have: \[\begin{array}{*{5}{c@{\hspace{0pt}}}} & 4 & 8 & \text{D} & 4_{16} \\ + & 5 & 9 & 2 & 5_{16} \\ \hline & & & F & 9_{16} \\ \end{array}\] So far so good. The next pair of digits is 8 + 9. Here’s where you want to be careful. You’re liable to look at “8+9" and immediately say “17!" But 8 + 9 is not 17 in hexadecimal. To figure out what it is, we start with the number 8, and count: “9…A…B… C…D…E…F…10…11…". The answer is “11," which of course is how you write “seventeen" in hex. So just like in grade school, we write down 1 and carry the 1: \[\begin{array}{*{5}{c@{\hspace{0pt}}}} & 1 & & & \\ & 4 & 8 & \text{D} & 4_{16} \\ + & 5 & 9 & 2 & 5_{16} \\ \hline & & 1 & F & 9_{16} \\ \end{array}\] Finally, our last digit is 4 + 5, plus the carried 1. We start with four and count off five: “5…6…7…8…9." Then we add the carry, and count “…A." The answer is A, with no carry, and so we have our final answer: \[\begin{array}{*{5}{c@{\hspace{0pt}}}} & 1& & & \\ & 4 & 8 & \text{D} & 4_{16} \\ + & 5 & 9 & 2 & 5_{16} \\ \hline & \textbf{A} & \textbf{1} & \textbf{F} & \textbf{9}_{\textbf{16}} \\ \end{array}\]

---

1. Sometimes numbers written in base 16 are called “hex numbers.”