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.