Algorithms to convert between binary, decimal and hexadecimal representation.

As we discussed in class, the word "algorithm" just means "method", but like most mathematical terms, there are special stipulations. The method always has to work, it must always take a finite amount of steps, and each step must take a finite amount of time to complete.

Decimal, or base 10, is the number system we are used to. Binary, or base 2, is the number system a computer uses, storing all its information as a string of 1s and 0s. Hexadecimal, or base 16, is kind like a compromise, a way to easily represent binary numbers in a way that takes less writing and is easier for the human programming the machines to read.

The algorithm from decimal to binary.

Start with a number written in decimal representation. We are going to build its equivalent binary representation bit by bit from the ones place to the twos place to the fours place, etc., which means building from right to left.

Step 0. Start with a decimal number and an empty representation for the binary equivalent.

Step 1. Is the ones digit of the decimal representation even or odd? If even, put a 0 in the first place to left of the current binary representation. If odd, put a 1 in the first place to the left of the current binary representation.

Step 2. Divide the current decimal representation by 2. If the result is more than 1, go to Step 1. If it is less than 1, STOP. We now have the correct binary representation of the original decimal number.

Example. Let's change 75dec to its binary equivalent.

Step 1a. 75 is odd so our current binary representation will be 1bin.
Step 2a. 75/2 = 37.5, bigger than 1, so we continue.
Step 1b. the ones place of 37.5 is odd so our current binary representation will be 11bin.
Step 2b. 37.5/2 = 18.75, bigger than 1, so we continue.
Step 1c. the ones place of 18.75 is even so our current binary representation will be 011bin.
Step 2c. 18.75/2 = 9.375, bigger than 1, so we continue.
Step 1d. the ones place of 9.375 is odd so our current binary representation will be 1011bin.
Step 2d. 9.375/2 = 4.6375, bigger than 1, so we continue.
Step 1e. the ones place of 4.6375 is even so our current binary representation will be 0 1011bin.
Step 2e. 4.6375/2 = 2.34375, bigger than 1, so we continue.
Step 1f. the ones place of 2.34375 is even so our current binary representation will be 00 1011bin.
Step 2f. 2.34375/2 = 1.171875, bigger than 1, so we continue.
Step 1g. the ones place of 1.17... is even so our current binary representation will be 100 1011bin.
Step 2f. 1.17.../2 = 0.58..., less than 1, so we STOP.

75dec = 100 1011bin

The algorithm from binary to decimal.

How can we check that 100 1011bin is equal to 75dec? The easiest way is to match up the bits that are 1s with the powers of 2 they correspond to in the binary representation. The powers of two, starting with 2^0 = 1, are as follows:

1, 2, 4, 8, 16, 32, 64,...

Match the powers from lowest to highest with the bits from right to left.

1 -> 1
2 -> 1
4 -> 0
8 -> 1
16 -> 0
32 -> 0
64 -> 1

That's all the bits in our string, so we add up the powers of two that correspond to the bits that are 1, which are marked in bold in the list above.

64 + 8 + 2 + 1 = 75 in base 10.


The algorithm from hexadecimal to binary and back.

If we take a bit string of length 4, we can represent all the numbers from 0 to 15 in decimal. The idea of hexadecimal is to have a single numeral represent each of these bit patterns, so this means we need a total of 16 symbols instead of ten. Hexadecimal uses a, b, c, d, e and f as the extra symbols and the pattern is as follows

binary hexadecimal
0000______0
0001______1
0010______2
0011______30100______4
0101______5
0110______6
0111______71000______8
1001______9
1010______a (corresponds to 10 in decimal)
1011______b (corresponds to 11 in decimal)
1100______c (corresponds to 12 in decimal)
1101______d (corresponds to 13 in decimal)
1110______e (corresponds to 14 in decimal)
1111______f (corresponds to 15 in decimal)

This is why we put the courtesy gaps between binary numbers every four places starting from the right. Read each four bit pattern and make the translation. If a bitstring has less than four bits, fill in leading zeros to make it a four bit long string. For example, 11bin would become 0011bin, which translates to 3hex. Or 101bin would become 0101bin, or 5hex.

The translation can work in either direction, so f1dhex = 1111 0001 1101bin.

The algorithm from hexadecimal to decimal.
Step 1: Take the first digit on the left of the hexadecimal number and change it to decimal. This means a becomes 10, b becomes 11, ... up to f becomes 15. If the digit is already 9 or less, you don't have to change it. This number is the first pass at your running total.

Step 2: If there are still more digits, multiply your running total by 16, change the next digit to decimal and add that to the running total. Continue with step 2 until all digits are exhausted.

Example: f1dhex. The first digit on the left is f, which corresponds to 15 in decimal, so the running total starts at 15.

There are more digits still, so we multiply the total by 16 and add the next digit.
15x16 + 1 = 241, our new running total.

We still have digits, so we multiply the running total by 16 and add the next digit d, which corresponds to 13.

241x16 + 13 = 3,856 + 13 = 3,869
That's the last digit, so we should be done. f1dhex = 3869dec.

The algorithm from decimal to hexadecimal.
One way to do this is to go from decimal to binary, then binary to decimal. Let's take 3869dec and change it to binary. If we did everything right in the steps above, we should get the binary number 1111 0001 1101, which translates into f1dhex.

dividing 3869 by two, looking at the ones digit for even or odd, then dividing the new number by two, again and again until the division produces a number less than 1

3869___ 9 is odd, so the first bit on the right is 1bin.
1934.5___ 4 is even, so the bits are now 01bin.
967.25___ 7 is odd, so the bits are now 101bin.
483.625___ 3 is odd, so the bits are now 1101bin.
241.8125___ 1 is odd, bits are 1 1101bin.
120.9...____ 0 is even, bits are 01 1101bin.
60.45...____ 0 is even, bits are 001 1101bin.
30.226...___ 0 is even, bits are 0001 1101bin.
15.113...____ 5 is odd, bits are 1 0001 1101bin.
7.5566...____ 7 is odd, bits are 11 0001 1101bin.
3.778..._____ 3 is odd, bits are 111 0001 1101bin.
1.889..._____ 1 is odd bits are 1111 0001 1101bin.
0.944... less than 1 so done. The final bit string is 1111 0001 1101bin.

That bitstring does correspond to the hexadecimal number we hoped we would get, f1dhex.

Here are some practice problems with solutions.