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.
Showing posts with label hexadecimal. Show all posts
Showing posts with label hexadecimal. Show all posts
Thursday, February 17, 2011
Friday, June 26, 2009
practice problems for changing bases
1) Change FADhex into decimal.
2) Change FADhex into binary.
3) Change 1,776dec into hexadecimal.
4) Change 1,776dec into binary.
5) Change 110 0101 0000 0110bin into hexadecimal.
6) Change 110 0101 0000 0110bin into decimal.
Answers in the comments.
2) Change FADhex into binary.
3) Change 1,776dec into hexadecimal.
4) Change 1,776dec into binary.
5) Change 110 0101 0000 0110bin into hexadecimal.
6) Change 110 0101 0000 0110bin into decimal.
Answers in the comments.
Labels:
binary,
decimal,
hexadecimal,
practice problems
Thursday, June 25, 2009
Binary and Hexadecimal representation
In computers, the machine only really understands two states, on and off, which we can represent with 1 and 0. This is called a binary system, and just like the decimal system, any number can be represented in binary by using the place holder system, so instead of just one on-off switch we ca have a series of on-off switches to represent more complex concepts and larger numbers.
It's very hard for people to read long strings of 1's and 0's, so a system where four bits are put together to represent a number between 0 and 15 was created. Base 16 is called hexadecimal, and we will see how to represent numbers in this system and switch back and forth between base 10, base 2 and base 16.
In base 10, when we count the number of digits in a number, we know the approximate size of the number a 4 digit number, like 2,678 or 5,321, is between 1,000 (10x10x10) and 10,000 (10x10x10x10). We call this the order of magnitude for a number, the largest power of ten needed to represent the value. The order of magnitude of an n digit number is n-1.
In binary, the number of digits tells us the largest power of two needed to represent the value. The powers of 2 from 2^0 to 2^10 are:
2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32
2^6 = 64
2^7 = 128
2^8 = 256
2^9 = 512
2^10 = 1,024
In base 2, we only have two symbols, 0 and 1. A binary digit is called a bit, and a series of 1's and o's is called a bitstring. When a number is represented in this part of the class, we will put the suffix bin, dec or hex behind it to show if it it the binary representation, the decimal representation or the hexadecimal representation.
Changing between bases
Example: 110 1101 1110 0101bin is a number represented in binary. (It is customary to put a space between digits to split them into packets of four bits.) Here is the method to turn this into a number represented in decimal.
Take the first bit on the left and put that into a variable we will call answer. If there are still bits in the string, multiply answer by 2 and add the next bit. We strip off the bits as we go.
110 1101 1110 0101bin answer=1.
10 1101 1110 0101bin answer=1*2+1 = 3.
0 1101 1110 0101bin answer=3*2+0 = 6.
1101 1110 0101bin answer=6*2+1 = 13.
101 1110 0101bin answer=13*2+1 = 27.
01 1110 0101bin answer=27*2+0 = 54.
1 1110 0101bin answer=54*2+1 = 109.
1110 0101bin answer=109*2+1 = 219.
110 0101bin answer=219*2+1 = 439.
10 0101bin answer=439*2+1 = 879.
0 0101bin answer=879*2+0 = 1,758.
0101bin answer=1,758*2+0 = 3,516.
101bin answer=3,516*2+1 = 7,033.
01bin answer=7,033*2+0 = 14,066.
1bin answer=14,066*2+1 = 28,133.
This means 110 1101 1110 0101bin = 28,133dec, which is to say in decimal representation, the standard way we write numbers. The thing is, there are a lot of chances to make mistakes. Base 16 was developed to be a bridge between machines that understand binary language and the people who program them. Since 16 = 2^4, if we have bitstrings of length four we can make sixteen distinct patterns, which represent the numbers from 0 to 15. Here are the patterns, with the idea that each bit represents a power of 2, specifically 8, 4, 2 and 1.
8421
_______ hex (decimal)
0000 -> 0
0001 -> 1
0010 -> 2
0011 -> 3
0100 -> 4
0101 -> 5
0110 -> 6
0111 -> 7
1000 -> 8
1001 -> 9
1010 -> A (10)
1011 -> B (11)
1100 -> C (12)
1101 -> D (13)
1110 -> E (14)
1111 -> F (15)
Using this table, it's easy to switch between binary and hexadecimal and vice versa, and changing from decimal to hexadecimal and vice versa is easier that the switch directly from decimal to binary.
110 1101 1110 0101bin = 6DE5hex
Switching from hexadecimal to decimal is like the method for switching from binary to decimal, expect that you multiply the answer by 16 at each step.
6DE5hex answer = 6
DE5hex answer = 6*16+D (13) = 109
E5hex answer = 109*16+E (14) = 1,758
5hex answer = 1,758*16 + 5 = 28,133
Notice that this is exactly the same answer as before, 218,133 in decimal, but it only took us four steps instead of fifteen.
Changing from decimal to another base is a matter of dividing by that base. Again, changing to hexadecimal is easier than changing to binary because there are less steps, and if we need binary, the switch back and forth between binary and hexadecimal is easy.
7,592dec into hex.
Divide 7,592 by 16 and we get 474, remainder 8. Answer = 8hex.
Divide 474 by 16 and we get 29, remainder 10. 10 becomes A in hex. Answer = A8hex.
Divide 29 by 16 and we get 1, remainder 13. 13 becomes D in hex. Answer = DA8hex.
Since 1 is less than 16, this is the last digit in our answer. Answer = 1DA8hex.
So the answer is 1DA8 in base 16, which we pronounce "one D A eight". Words like "thousand" and "hundred" only have meaning in base 10. If we want the answer in binary, it's easy to change the hex digits into bits.
1DA8hex = 0001 1101 1010 1000bin
In a computer, the pattern might include all the bits, including the leading zeros, but we might also write the answer without the leading zeros as 1 1101 1010 1000bin.
The notes for these topics are on pages 20 to 23.
It's very hard for people to read long strings of 1's and 0's, so a system where four bits are put together to represent a number between 0 and 15 was created. Base 16 is called hexadecimal, and we will see how to represent numbers in this system and switch back and forth between base 10, base 2 and base 16.
In base 10, when we count the number of digits in a number, we know the approximate size of the number a 4 digit number, like 2,678 or 5,321, is between 1,000 (10x10x10) and 10,000 (10x10x10x10). We call this the order of magnitude for a number, the largest power of ten needed to represent the value. The order of magnitude of an n digit number is n-1.
In binary, the number of digits tells us the largest power of two needed to represent the value. The powers of 2 from 2^0 to 2^10 are:
2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32
2^6 = 64
2^7 = 128
2^8 = 256
2^9 = 512
2^10 = 1,024
In base 2, we only have two symbols, 0 and 1. A binary digit is called a bit, and a series of 1's and o's is called a bitstring. When a number is represented in this part of the class, we will put the suffix bin, dec or hex behind it to show if it it the binary representation, the decimal representation or the hexadecimal representation.
Changing between bases
Example: 110 1101 1110 0101bin is a number represented in binary. (It is customary to put a space between digits to split them into packets of four bits.) Here is the method to turn this into a number represented in decimal.
Take the first bit on the left and put that into a variable we will call answer. If there are still bits in the string, multiply answer by 2 and add the next bit. We strip off the bits as we go.
110 1101 1110 0101bin answer=1.
10 1101 1110 0101bin answer=1*2+1 = 3.
0 1101 1110 0101bin answer=3*2+0 = 6.
1101 1110 0101bin answer=6*2+1 = 13.
101 1110 0101bin answer=13*2+1 = 27.
01 1110 0101bin answer=27*2+0 = 54.
1 1110 0101bin answer=54*2+1 = 109.
1110 0101bin answer=109*2+1 = 219.
110 0101bin answer=219*2+1 = 439.
10 0101bin answer=439*2+1 = 879.
0 0101bin answer=879*2+0 = 1,758.
0101bin answer=1,758*2+0 = 3,516.
101bin answer=3,516*2+1 = 7,033.
01bin answer=7,033*2+0 = 14,066.
1bin answer=14,066*2+1 = 28,133.
This means 110 1101 1110 0101bin = 28,133dec, which is to say in decimal representation, the standard way we write numbers. The thing is, there are a lot of chances to make mistakes. Base 16 was developed to be a bridge between machines that understand binary language and the people who program them. Since 16 = 2^4, if we have bitstrings of length four we can make sixteen distinct patterns, which represent the numbers from 0 to 15. Here are the patterns, with the idea that each bit represents a power of 2, specifically 8, 4, 2 and 1.
8421
_______ hex (decimal)
0000 -> 0
0001 -> 1
0010 -> 2
0011 -> 3
0100 -> 4
0101 -> 5
0110 -> 6
0111 -> 7
1000 -> 8
1001 -> 9
1010 -> A (10)
1011 -> B (11)
1100 -> C (12)
1101 -> D (13)
1110 -> E (14)
1111 -> F (15)
Using this table, it's easy to switch between binary and hexadecimal and vice versa, and changing from decimal to hexadecimal and vice versa is easier that the switch directly from decimal to binary.
110 1101 1110 0101bin = 6DE5hex
Switching from hexadecimal to decimal is like the method for switching from binary to decimal, expect that you multiply the answer by 16 at each step.
6DE5hex answer = 6
DE5hex answer = 6*16+D (13) = 109
E5hex answer = 109*16+E (14) = 1,758
5hex answer = 1,758*16 + 5 = 28,133
Notice that this is exactly the same answer as before, 218,133 in decimal, but it only took us four steps instead of fifteen.
Changing from decimal to another base is a matter of dividing by that base. Again, changing to hexadecimal is easier than changing to binary because there are less steps, and if we need binary, the switch back and forth between binary and hexadecimal is easy.
7,592dec into hex.
Divide 7,592 by 16 and we get 474, remainder 8. Answer = 8hex.
Divide 474 by 16 and we get 29, remainder 10. 10 becomes A in hex. Answer = A8hex.
Divide 29 by 16 and we get 1, remainder 13. 13 becomes D in hex. Answer = DA8hex.
Since 1 is less than 16, this is the last digit in our answer. Answer = 1DA8hex.
So the answer is 1DA8 in base 16, which we pronounce "one D A eight". Words like "thousand" and "hundred" only have meaning in base 10. If we want the answer in binary, it's easy to change the hex digits into bits.
1DA8hex = 0001 1101 1010 1000bin
In a computer, the pattern might include all the bits, including the leading zeros, but we might also write the answer without the leading zeros as 1 1101 1010 1000bin.
The notes for these topics are on pages 20 to 23.
Subscribe to:
Posts (Atom)