Introduction to Binary and Hexadecimal
Atrevida Game Programming Tutorial #1
Understanding binary and hexadecimal numbers is essential for systems-level
programming. Binary numbers are important because the computer "works with"
binary numbers -- numbers composed of two digits, 1 and 0. Hexadecimal
numbers are convenient because they allow us to handle binary numbers easily.
The number system that we are accustomed to using is the decimal system. Decimal numbers can consist of ten digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. For this reason, decimal is often referred to as the base-ten system. Notice that any number, no matter how large or small, can be represented with combinations of those ten digits (and a decimal point).
Alternate number base systems simply change the number of digits in the "alphabet" of available digits. For example, let us create a new numbering system. In our number system, we will only use eight digits in our alphabet of digits. We have to include zero in the alphabet, so our eight digits will be 0, 1, 2, 3, 4, 5, 6, and 7. This numbering system is actually called octal.
With octal, we can do mathematical operations such as addition, subtraction, multiplication, and division, just like we can in decimal. So, in octal, we could say that two plus five equals seven, or four minus one is three. But, what happens if we get a number that exceeds seven, the biggest digit in our octal alphabet? For that matter, how do we count in octal?
Well, first consider counting in decimal. If we ignore zero in our counting, as we usually do (outside of the computer world), we count: 1, 2, 3, 4, 5, 6, 7, 8, 9. But now we have run out of single digits in our decimal alphabet! So we put a one in the tens place, and put a zero in the units (ones) place, and we get 10. Then we continue counting: 10, 11, 12, 13, 14, 15, 16, 17, 18, 19. But we've run out of digits in the units place again! So we bump up the tens place digit from 1 to 2, and we reset the units place to zero again. And we continue counting: 20, 21, 22, 23, 24, 25, and so on. When we reach 99, we've exhausted all of the digits in both the tens and units places. So we put a one in the hundreds place, and zeroes in the tens and units places, and we get 100.
Another way of thinking about this is to imagine all of the possible unoccupied "places" in a number to be zeroes. Then, every time we run out of digits in the units place, we add one to the place to the left, and change the units place to zero. If the ten's place runs out of digits, then we add one to the place to the place to the left, and so on. (Adding one to a number is also called incrementing that number, and subtracting one from a number is also called decrementing that number.) Essentially, the plan is: if, when counting, a place "runs out of" digits, set that place's digit to zero and increment the digit at the place to the left. If that place has run out of digits, then repeat: set that place's digit to zero and increment the digit to the place to the left, and so on.
Now, the original question was about counting in octal. Can we use this "rule" to count in octal? Yes we can, as long as we remember what the octal alphabet is -- we "run out of digits" when we try to go past seven. So, if we start at 1, we can count: 1, 2, 3, 4, 5, 6, 7. Then we increment the place to the left of the units place (which is zero to start), and put a zero in the units place, to get 10. This is the eighth number we've counted so far, so 10 in octal must be equivalent to 8 in decimal! If we continue to count, we get 11 (equal to 9 in decimal), 12 (equal to 10 in decimal), 13 (equal to 11 in decimal), and so on, until we reach 17 octal. Now we increment the place to the left of the units place, and set the units place to zero again, to get 20 octal.
As you can see, it can easily become confusing to keep track of what an octal number is equivalent to in decimal, so methods of converting numbers of different bases will be described later. And it can be even more difficult to tell what base a given number is in: for example, if you saw the number "35", would you be able to tell whether it is a decimal or octal number? If you read the number 35 in everyday literature, you could very safely assume that the number is in decimal. But if you were reading a technical document using both octal and decimal numbers, it would be impossible to tell, if no clues were provided, which base the number is in (35 could be an octal number because both digits, 3 and 5, are within the octal alphabet). From now on, when I use an octal number, I'll write "oct" or "OCT" after the number. This is fairly standard; another fairly common standard is to write a "q" or "Q" after a octal number. I have also seen a subscripted "8" written to the left or the right of a number in octal; I personally don't use this format because it can't be written easily on a computer, and on paper it is easy to write subscripts sloppily and have the numbers run together. Decimal numbers can be postfixed with "dec" or "DEC", although in many cases it is okay to omit it and simply assume that readers know that you are using decimal.
Just for review, here is a short table of the first twenty-four numbers encountered when counting in decimal and octal:
Dec: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Oct: 1 2 3 4 5 6 7 10 11 12 13 14 15 16 17 20 21 22 23 24 25 26 27 30
Now, if we wanted to, we could use the above table as a number line, and add 12 oct and 16 oct, to get 30 oct. It is sometimes easier to convert numbers of different bases into decimal, do the arithmetic with the familiar decimal system, and then convert the result back to the desired number base. If converting is too time consuming, you can construct addition and multiplication tables, just like the ones you may have had to memorize ing rade school, to help you do arithmetic in the "native" number base of your choice. Addition and subtraction for other number bases use the same rules as they do for decimal, except they take into account the different digit "alphabets" for each base. (An example will be given later.)
The binary number systemNow that we are reasonably comfortable with an alternate number base, octal, we can now focus our interests on binary. (Octal does occasionally have uses in electronics and programming, although we really won't be using it for anything else here.) Binary is just another number system with a base other than ten. It is a base-two system, and so its alphabet of digits consists solely of the two digits 0 and 1. This may seem strange at first, but if we use our informal "rule" suggested above, we can confidently count in binary.
If we ignore 0, we start counting with 1. But we can't go any farther; we've run out of digits in the alphabet already! So we increment the digit in the place to the left, and reset the current place's digit to zero, and we get 10. And this 10 in binary is equivalent to 2 in decimal, because it is the second number we've counted. (This may seem strange, but recall that in octal, 10 oct equals 8 dec. You may see a pattern developing: 10 in binary is equal to 2 dec, and binary is a base-two system; 10 in octal is equal to 8 dec, and octal is a base-eight system...) To continue, we count from 10 to 11, and then we must increment the digit in the place to the left of both digits, and reset both digits to zero. We get 100 in binary. You may see patterns developing as we count further: 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, etc. For example, the right-most digit (also called the least significant digit) flips back and forth from 0 to 1 and back to 0 for each consecutive number. The digit just left to the right-most digit (we can call it the second-least significant digit) follows the pattern 0, 0, 1, 1, 0, 0, 1, 1, etc. Can you find any other such patterns (you might want to use the table below)?
For a review, and to compare with octal, here is a table of decimal, octal, and binary numbers:
Decimal Octal Binary ------------------------------------------------ 0 0 0 1 1 1 2 2 10 3 3 11 4 4 100 5 5 101 6 6 110 7 7 111 8 10 1000 9 11 1001 10 12 1010 11 13 1011 12 14 1100 13 15 1101 14 16 1110 15 17 1111 16 20 10000
To differentiate between numbers in binary and other number bases (after all, "1011" could be in decimal, octal, or binary), we can write "bin" or "BIN" after the number. Often, you will see a "b" or "B" is written after the number, with an extra zero prefixed to the number, like this: "1010 bin" becomes "01010b".
Mathematical operations with binary can get tricky, as you can imagine, although all you really need to know how to do is addition with binary numbers. (Subtraction can be done by adding a negative number to another number, but we'll cover this in another chapter. Multiplication can be done by repeating additions over and over a given number of times; division can be done by subtracting a number over and over.)
Addition in binary follows the same rules as addition in decimal. To make things easier, here's the addition table for binary:
| 0 | 1 ---+-------+------- 0 | 0 | 1 ---+-------+------- 1 | 1 | 10(*) (*) or "0, and carry a 1"
So, say we need to add 01100100 bin to 01110101 bin. If we write it as...
( columns: 76543210 |||||||| |||||||| ) 01100100 bin + 01110101 bin ------------
...we can add the 0 and 1 in column zero, and, checking the table, we get 1. (Write this 1 underneath the line, just like in decimal addition.) Then, moving to column 1, 0 + 0 = 0, so write down a 0. In column 2, 1 + 1 gives us 10 bin. Just like in decimal addition, we write down the right-most value, 0, and carry the 1. In column 3, we add the carried 1 to 0 + 0 and get 1. In column 4, 0 + 1 = 1. In column 5, 1 + 1 = 10 bin, so we write down the 0 and carry a 1 again. In column 6, we add the carried 1 to 1 + 1 again, and get 11. What do we do here? We can write down the right-most 1, and then carry the left-most 1. And in column 7, we get 1 + 0 = 1. Our result is 11011001 bin.
The hexadecimal number systemOften it becomes tedious to write and remember long binary numbers. As we will see in the next chapter, it is normal in PC programming to encounter binary numbers that are eight, sixteen, or thirty-two digits in length. Hexadecimal offers us a convenient "shorthand" for binary numbers.
The hexadecimal number system is just another number base system; its alphabet of digits consists of sixteen single digits, so it is the base-sixteen number system. This presents a problem: the decimal system that we are familiar with has only ten number symbols, so how should we define our hexadecimal alphabet? We could define any symbols we want for the digits past 9. We could use shapes, such as a square for the tenth digit, a triangle for the eleventh digit, and so on, or we could use Greek letters, or any other such scheme. But it is easiest just to use letters from our normal English alphabet to stand for these extra digits. The commonly used hexadecimal alphabet is as follows: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F. To differentiate between hexadecimal numbers and numbers of other bases, we can write "hex" or "HEX" after the number. (Or, we can prefix an extra zero to the number and put a "h" or "H" after the number, like this: "3F9B hex" becomes "03F9Bh". In the next chapter we will see language- specific syntaxes for hex numbers.)
Counting in hexadecimal uses the same "rules" as in any number base, as we have seen previously with decimal, octal, and binary. We count 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A (equal to 10 dec), B (11 dec), C (12 dec), D (13 dec), E (14 dec), and F (15 dec). Then we continue with 10 (16 dec), 11 (17 dec), and so on up to 1F (31 dec), and then we get 20 (32 dec), 21 (33 dec), etc.
Here is one last table listing numbers in decimal and their binary, octal, and hexadecimal equivalents. For practice, you may wish to write out the table and extend it for some more numbers (say, to 20 hex). At the very least, write or print out the table from 0 hex to F hex, as we'll be referring to this part of the table rather frequently:
Decimal Octal Binary Hexadecimal -------------------------------------------------------------- 0 0 0 0 1 1 1 1 2 2 10 2 3 3 11 3 4 4 100 4 5 5 101 5 6 6 110 6 7 7 111 7 8 10 1000 8 9 11 1001 9 10 12 1010 A 11 13 1011 B 12 14 1100 C 13 15 1101 D 14 16 1110 E 15 17 1111 F 16 20 10000 10 17 21 10001 11 18 22 10010 12 19 23 10011 13 20 dec 24 oct 10100 bin 14 hex
From what we've seen so far, hexadecimal doesn't look very interesting -- it just seems more complicated than using ordinary decimal numbers. But if we take a closer look at some of the two-digit hex numbers in the above table, and we look at the binary numbers beside them, we might notice some interesting properties. Namely, notice how the binary patterns for 0 hex through to F hex begin to repeat in the four right-most digits in the binary patterns for 10 hex through to 1F hex. In fact, if we keep extending the table, we notice that these patterns continue periodically; that is, every sixteen hexadecimal numbers, this pattern repeats. Then notice that every time the "0000" occurs in the right-most four digits of a binary number, the right-most digit in the hexadecimal number is a zero. Every time "0001" occurs in that position, the hexadecimal number is a one. Every time we see "0002", the hexadecimal number is a two. Continuing the pattern up to F hex, we notice that for a "1111" in this position in the binary number, the corresponding hex digit is an "F".
This is an interesting pattern. Does it occur elsewhere? Actually, yes, if we had the patience to extend the table to FF hex or beyond, and we looked at the four digits to the left of the right-most four digits, we would notice this pattern repeating itself again! We would see "0000" in the table, and associate that with a zero in the hexadecimal number. And we would see "0001" in the table, and we would see a corresponding one in the hexadecimal number. (Mind you, there would be a set of sixteen "0000"'s in a row if we scanned down the table, then sixteen "0001"'s, and so on.)
So we have "discovered" an interesting relationship between hexadecimal and binary numbers. A set of four binary digits is equivalent to a single hexadecimal digit. We can see this with the first sixteen entries in the above table -- 0000 bin is equivalent to 0 hex, 0001 bin is equivalent to 1 hex, and so on. 1101 bin is the same as D hex.
This relationship gives us a clever method of converting binary numbers to hexadecimal. We start at the right of a given binary number and work left, and consider four-digit chunks of the binary number. We can consult our table for each four-digit pattern we encounter, and write down the corresponding hexadecimal digit. (Make sure the hex digits are written in the same right-to-left order as the chunks of binary!)
This conversion is best explained with an example. We want to convert the ugly-looking 100110100110101 bin to hexadecimal. First, let's break up the number into four-digit chunks, starting from the right. Any left-over digits on the left can be considered as a four-digit number (add zeroes to the left if necessary):
0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 1
Now, we can consult the table. We see that 0101 bin is equivalent to 5 hex, 0011 bin is the same as 3 hex, 1101 bin equals D hex, and 0100 equals 4 hex. Writing these in the correct order, we get 4D35 hex. If you want to try some more examples, see if you can convert these binary numbers to hex: a. 11001010 bin, b. 0110110000 bin, and c. 1100111101011001 bin. Check your answers with mine: a. CA hex, b. 1B0 hex, and c. CF59 hex.
Converting from hexadecimal to binary is even easier: just replace every hex digit you see with its binary equivalent. For example, for 2E9A hex, the 2 expands to 0010 bin, the E expands to 1110 bin, the 9 expands to 1001 bin, and the A expands to 1010 bin. Concatenating (combining) these together, we get 0010111010011010 bin. If you want some practice, try converting these to binary: a. 57 hex, b. 1A7D hex, and c. 3FC hex. My results were: a. 01010111 bin, b. 0001101001111101 bin, and c. 001111111100 bin.
Recall that the basic mathematical operations, addition, subtraction, multiplication, and division, work the same way with hexadecimal numbers as they do with decimal numbers. However, when doing arithmetic with hexadecimal, I find it very useful to construct hexadecimal addition and multiplication tables. For lengthy calculations, I prefer to avoid headaches and save time by converting hex numbers to decimal and then changing the results back to hex.
Now that we've had a brief taste of hexadecimal, you can see that it is often faster to refer to hex numbers instead of their binary equivalents. The quick conversion between binary and hex is probably hexadecimal's strongest trait; I wish there were methods of converting binary to and from decimal that are as quick as those for hexadecimal. But if you're still uncomfortable with hex, keep in mind that you use can still use decimal numbers in many situtations.
Conversion of numbers to and from different number basesWe have discussed converting numbers to and from binary and hexadecimal, but those tricks don't usually work with other number bases. Here I will describe methods for converting numbers to and from decimal and binary, which are probably amongst the most common converting tasks. I will also briefly show how these methods can be generalized for use with other number bases.
Imagine that we want to know what 110101 bin represents in decimal. We could extend our conversion table given above until we reached this particular binary number, but of course that's impractical. But let's consider how we could re-write a decimal number first. Say we have the number 576 dec. We can re-write this as 500 + 70 + 6, or:
2 1 0 5 * 10 + 7 * 10 + 6 * 10
Let's consider the exponents (the superscripts). We can refer to each place in the number by its exponent, so the units place is place 0, the tens place is place 1, the hundreds place is place 2, and so on. Now notice that the bases in that expression are 10's. Recall that decimal is a base-ten system. Given this hint, we can try expressing numbers in other bases in a similar form, say, in binary. Let's take our 110101 bin example:
5 4 3 2 1 0 110101 bin = 1 * 2 + 1 * 2 + 0 * 2 + 1 * 2 + 0 * 2 + 1 * 2 dec
A 2 is used instead of 10 because binary is a base-two system. Now we can evaluate the expression we have constructed. (Remember that a number to the power of zero equates to one. And, of course, multiplying anything by zero equates that term to zero.) So, evaluating this expression, we get 32 + 16 + 0 + 4 + 0 + 1, or 53 dec.
Basically, we can use method this to convert a number in any base to base ten -- just change the 2 to the number of the base. For example, to change a hexadecimal number to decimal, use 16 instead of 2, because hex is a base-sixteen number system. Here's an example: we'll convert 3DA hex to decimal:
2 1 0 3DA hex = 3 * 16 + 13 * 16 + 10 * 16 = 242 dec
Notice that I converted D hex to 13 dec, and A hex to 10 dec. (If you wish, you can use the conversion table.) Then, it becomes a simple matter to evaluate the expression.
Another method which I like to use is to draw a quick diagram. Here is the number 01100011 bin, surrounded in boxes. Above each box is the base of the number, with each base having an exponent equal to the number of the place which it represents, that is:
7 6 5 4 3 2 1 0 2 2 2 2 2 2 2 2 +---+---+---+---+---+---+---+---+ | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | +---+---+---+---+---+---+---+---+
Now it is easy to look at the digits inside the boxes, and for each one that is not a zero, you can add to a total the product of that digit and the expression above it. So for the above example, we get 1 * 2^6, plus 1 * 2^5, plus 1 * 2^1, plus 1 * 2^0, and the sum of these products is 99 dec.
To save time, you can write the numbers 1, 2, 4, 8, 16, etc. above the boxes instead of the base and exponents:
2^0 = 1 2^1 = 2 2^2 = 4 2^3 = 8 2^4 = 16 2^5 = 32 2^6 = 64 2^7 = 128, etc.
We'll be seeing more diagrams like these in the further chapters.
Finally, we often want to convert decimal numbers to binary (or some other base). To do this, we can repeatedly divide the decimal number by the base we to which we are converting (so for binary, we keep dividing the decimal number by 2). We can use the remainders (also called modulos) of each division to construct our new number. As this is difficult to explain, I'll show some examples. Say we want to convert 235 dec to binary. We start by dividing 235 dec by the base we wish to convert to, which is 2. Then we divide that result by 2, and then we divide that result by 2, and so on. We stop when we get a zero as a quotient. We must keep track of the remainders from each step:
235 / 2 = 117, remainder 1 117 / 2 = 58, remainder 1 58 / 2 = 29, remainder 0 29 / 2 = 14, remainder 1 14 / 2 = 7, remainder 0 7 / 2 = 3, remainder 1 3 / 2 = 1, remainder 1 1 / 2 = 0, remainder 1.
Now, if we read the remainders backwards (from the bottom to the top), we get 11101011 bin. This is how you would represent 235 dec in binary.
Let's try converting 49 dec to octal:
49 / 8 = 6, remainder 1 6 / 8 = 0, remainder 6.
Going from bottom to top, we read off a 6 and then a 1. We get 61 oct, so 49 dec = 61 oct.
An alternate method, which can be faster in some cases and slower in others, is to draw the box diagram and then try plugging in combinations of numbers in the boxes until the sum of the products of the numbers in the boxes and the expression above them equals your decimal number. For small numbers, this is much quicker: in a decimal to binary conversion, you can tell very quickly that, say, 9 dec can be created by adding an 8 and a 1; you can then put ones in the places associated with the 8 and 1, and put zeroes everywhere else. We'll become more familiar with these diagrams in the later chapters, so don't worry if this is confusing right now.
SummaryNow we're familiar with number bases other than decimal. In particular, we've used binary, octal, and hexadecimal numbers. We've seen how to convert between decimal and other bases, and we've seen faster methods for converting binary to and from hexadecimal. We've also grown aware of the fact that many of the "rules" of counting and doing arithmetic in alternate number bases are the same as in our familiar decimal system.
If you're not sure if you understand a certain topic, I'd encourage you to go back and skim through any sections that you're unsure about. If you want a different explanation of these topics, you might also want to look at some books on assembly language, as just about every assembly language book has a chapter or two at the start that deals with binary and hexadecimal numbers. (Try your library first. Preferably find a book on PC assembly language; IBM PC's use Intel 80x86 processors (eg. 8088, 8086, 286, 386, 486, Pentium, etc.))
One last note: I'd also like to point out that there are programmers' calculators available that can handle conversions between different number bases. Chances are you don't really need one (I seem to find myself doing fewer and fewer conversions as time goes on), but if you find yourself doing lots of conversions and math using less familiar number systems, you might want to consider finding one.