« Learn Hexadecimal and Binary | Rvalue References Applied » |
I have started writing an entry that discusses the value of becoming familiar with the binary (base-2) and hexadecimal (base-16) number systems because they are generally more useful to a programmer than decimal (base-10). My daughter is currently in high-school and she is taking a programming course. One of the things that she is currently learning how to do is count in binary. So I decided to expand my explanation of conversion between number systems as a reference for her and all of those who would like a refresher. The entry following this one will describe how binary and hexadecimal will make you a more effective programmer.
Place Value: coefficient·radixplace
To be able to convert numbers between different numerical bases, it is important to review the concept of place value. Each place, or column, in a number represents a value equal to number system base raised to the power of its place index starting at 0. The official name of the base-value is the radix. For example, consider the first three place values for a number system that has a radix of b.
b2+b1+b0
If we are dealing with decimal (base-10), the radix = 10 and we would have place values of:
102 + 101 + 100
Now we have the 1's column, 10's column, and 100's column:
100 + 10 + 1
The number stored at each column in the number is called the coefficient. To construct the final number, we multiply the coefficient by its place-value and add the results at each place together. Here is the decimal number 237 broken down by place value:
2·b2 +3·b1 +7·b0
2·102 + 3·101 + 7·10
200 + 30 + 7
237
Hopefully decimal form is so natural to you that 237 seems like a single number, rather than the sum of place values that are multiplied by their coefficient.
The Binary Number System
There are 10 types of people, those that understand binary and those that don't
If you are wondering what the eight other types of people are, continue reading.
Binary is a base-2 number system. This means that each column in a binary number represents a value of 2 raised to the power of its place index. A number system requires a number of symbols to represent each place value that is equal to its Base value, and zero is always the first symbol to include in this set. For instance, decimal (base ten) requires ten symbols: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Therefore, binary (base two) only requires two symbols: {0, 1}.
Adding the radix as a subscript after a number is a common notation to indicate the base-value of a number when there is a possibility for confusion. Unless the context specifically indicates a different number system, decimal form is assumed. For example, the value 2 in binary:
102 = 210
If we had used that notation in the joke at the beginning... well, it just wouldn't have been as funny.
Another place that you will see the subscript notation is when you study logarithms:
logax = logbx / logba
I'll leave the details for logarithms for another time.
Counting in Binary
When learning anything new, it can be helpful to map something that you already know to the new topic. For a new number system, counting with both number systems can be a helpful exercise. Counting in all number systems uses the same process:
- Start with zero in the least significant column
- Count up until you have used all of the symbols in increasing order in the least significant, 1's, column
- When the limit is reached, increment the value in the next column, and reset the current column to zero.
- If the next column has used all of the symbols, increment the column after that and reset the current column.
- Once no further columns reach their limit, return to step 2 to continue counting.
Starting with decimal, if we count up from zero to 9, we get:
0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 ...roll over
We are now at step 3, we have reached the limit, so we increment the next column from an implied 0 to 1, and reset the current column for the result of:
10
Continuing to count, we increment the 1's column and rolling over the successive columns as necessary:
11 - 12 - 13 ... 98 - 99 ... roll over
100
Here is 0-15 in binary. When working with computers, and binary in general, you will typically see zeroes explicitly written for the more significant columns. We require 4 binary digits to represent 15.
Binary | Sum of Columns | Decimal | ||
0000 | 0 + 0 + 0 + 0 | 0 | ||
0001 | 0 + 0 + 0 + 1 | 1 | ||
0010 | 0 + 0 + 2 + 0 | 2 | ||
0011 | 0 + 0 + 2 + 1 | 3 | ||
0100 | 0 + 4 + 0 + 0 | 4 | ||
0101 | 0 + 4 + 0 + 1 | 5 | ||
0110 | 0 + 4 + 2 + 0 | 6 | ||
0111 | 0 + 4 + 2 + 1 | 7 | ||
1000 | 8 + 0 + 0 + 0 | 8 | ||
1001 | 8 + 0 + 0 + 1 | 9 | ||
1010 | 8 + 0 + 2 + 0 | 10 | ||
1011 | 8 + 0 + 2 + 1 | 11 | ||
1100 | 8 + 4 + 0 + 0 | 12 | ||
1101 | 8 + 4 + 0 + 1 | 13 | ||
1110 | 8 + 4 + 2 + 0 | 14 | ||
1111 | 8 + 4 + 2 + 1 | 15 |
The Hexadecimal Number System
Hexadecimal is a base-16 number system. Therefore, we will need sixteen symbols to represent the place values. We can start with the ten numbers used in decimal, and we use letters of the alphabet to represent the remaining six symbols. Although letter-case can matter in programming, the letters used in hexadecimal are case-insensitive. Here is a mapping of the hexadecimal values to decimal:
Decimal: | { | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | } |
Hexadecimal: | { | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | } |
Number Base Conversion
Let's discuss how to convert between number systems with different base values. Specifically, we will describe how to convert from "Decimal to Basex" and "Basex to Decimal".
Decimal to Basex
Here is the algorithm to convert a number in decimal to a different base:
- Divide the decimal number by the radix of the target base
- The remainder from step 1 becomes the value for the current column.
- Use the quotient (answer) from step 1 as the decimal value to calculate the next column.
- Return to step 1 and repeat until the quotient is zero.
Let's return to the number 237 and convert it to a binary number:
decimal: | 237 | |||||
radix: | 2 | |||||
Decimal | Radix | Quotient | Remainder | |||
237 | / | 2 | 118 | 1 (20) | ||
118 | / | 2 | 59 | 0 (21) | ||
59 | / | 2 | 29 | 1 (22) | ||
29 | / | 2 | 14 | 1 (23) | ||
14 | / | 2 | 7 | 0 (24) | ||
7 | / | 2 | 3 | 1 (25) | ||
3 | / | 2 | 1 | 1 (26) | ||
1 | / | 2 | 0 | 1 (27) | ||
binary: | 11101101 |
Here is 237 converted to a hexadecimal number:
decimal: | 237 | |||||
radix: | 16 | |||||
Decimal | Radix | Quotient | Remainder | |||
237 | / | 16 | 14 | D16 (13) (160) | ||
14 | / | 16 | 0 | E16 (14) (161) | ||
hexadecimal: | ED16 |
A common notation to represent hexadecimal when dealing with computers and in programming languages themselves, is to prepend an 'x' in front of the number like so: xED
.
Here is one more decimal-to-hexadecimal example:
decimal: | 3,134,243,038 | |||||
radix: | 16 | |||||
Decimal | Radix | Quotient | Remainder | |||
3,134,243,038 | / | 16 | 195,890,189 | E (14) (160) | ||
195,890,189 | / | 16 | 12,243,136 | D (13) (161) | ||
12,243,136 | / | 16 | 765,196 | 0 ( 0) (162) | ||
765,196 | / | 16 | 47,824 | C (12) (163) | ||
47,824 | / | 16 | 2,989 | 0 ( 0) (164) | ||
2,989 | / | 16 | 186 | D (13) (165) | ||
186 | / | 16 | 11 | A (10) (166) | ||
11 | / | 16 | 0 | B (11) (167) | ||
hexadecimal: | xBAD0C0DE |
Basex to Decimal
Actually, I have already demonstrated how to convert a number from a base different than ten, into decimal. Once again, here is the complete formula, where cx represents the coefficients at each place-column.
cn·bn + ... + c2·b2 + c1·b1 + c0·b0
As an example, let's convert the binary answer back into decimal:
1·27 + 1·26 + 1·25 + 0·24 + 1·23 + 1·22 + 0·21 + 1·20
1·128 + 1·64 + 1·32 + 0·16 + 1·8 + 1·4 + 0·2 + 1·1
128 + 64 + 32 + 8 + 4 + 1
237
Basex to Basey
Is it possible to convert a number from Basex directly to Basey without converting to decimal (base-10) first?
Yes, however, you will need to perform all of your math operations in either Basex or Basey. The algorithms that I have presented are performed with base-10 since that is the number system most people are familiar with.
Demonstration
Here is a short demonstration program to convert a decimal number into a value of any numeral base between 2-36.
Why between those two ranges?
Try to imagine how a base-1 number system would work with only the symbol {0} to work with. Alternatively, we can combine the numerical set: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} with the alphabetic set: {A, B, C ... X, Y, Z} to create a set of 36 symbols.
C++
// The set of possible symbols for representing other bases. | |
const char symbols[] = {'0', '1', '2', '3', '4', '5', | |
'6', '7', '8', '9', 'A', 'B', | |
'C', 'D', 'E', 'F', 'G', 'H', | |
'I', 'J', 'K', 'L', 'M', 'N', | |
'O', 'P', 'Q', 'R', 'S', 'T', | |
'U', 'V', 'W', 'X', 'Y', 'Z'}; |
Here is the base-conversion algorithm from above written in C++.
C++
void ConvertToBase( const unsigned long decimal, | |
const unsigned long radix) | |
{ | |
unsigned long remainder[32] = {0}; | |
unsigned long quotient = decimal; | |
unsigned char place = 0; | |
| |
while (0 != quotient) | |
{ | |
unsigned long value = quotient; | |
remainder[place] = value % radix; | |
quotient = (value - remainder[place]) / radix; | |
| |
place++; | |
} | |
| |
cout << decimal << " in base " << radix << " is "; | |
| |
for (unsigned char index = 1; index <= place; index++) | |
{ | |
cout << symbols[remainder[place - index]]; | |
} | |
} |
The values are from the examples above. You can modify the values that are used with the function calls to ConvertToBase
in the program below:
C++
int main(int argc, char* argv[]) | |
{ | |
ConvertToBase(237, 2); | |
ConvertToBase(237, 10); | |
ConvertToBase(237, 16); | |
ConvertToBase(3134243038, 16); | |
ConvertToBase(3134243038, 36); | |
| |
return 0; | |
} |
Output:
237 in base 2 is 11101101 237 in base 10 is 237 237 in base 16 is ED 3134243038 in base 16 is BAD0C0DE 3134243038 in base 36 is 1FU1PEM
Summary
Ever since you learned to count in decimal you have been using exponents with a base-10; it's just that no one ever made a big deal of this fact. To use a different numeral system, such as binary (base-2) or hexadecimal (base-16), you simply need to determine a set of symbols to represent the values and you can use the same counting rules that you use in base-10, except that you have a different number of symbols. Converting between any number system is possible, however, it is simplest to convert to decimal first if you want to continue to use base-10 arithmetic operations.
Recent Comments