A-level Computing 2009/AQA/Processing and Programming Techniques/Data Representation in Computers

Hexadecimal.
As you know, the number system we normally count in is base 10, and the number system that computers use, binary, is base 2. Hexadecimal is a base 16 number system. In hexadecimal, the numbers 0-9 are used, just like in denary, but the letters A-F are also used to represent the numbers 10-15. The table below shows the numbers 0-16 in denary, and their binary and hexadecimal equivalents:
You may notice from the table that one hexadecimal digit can represent exactly 4 binary bits. Hexadecimal is useful to us as a shorthand way of writing binary, and makes it easier to work with long binary numbers.
Converting Between Bases.
Since 4 binary bits are represented by one hexadecimal digit, it is simple to convert between the two. You can group binary bits into groups of 4, starting from the right, and adding extra 0's to the left if required, and then convert each group to their hexadecimal equivalent. For example, the number 110110011110101 can be written like this:
0110 1100 1111 0101
and then by using the table above, you can convert each group of 4 bits into hexadecimal:
6 C F 5.
So the binary number 0110110011110101 is 6CF5 in hexadecimal. We can check this by converting both to denary. First we'll convert the binary number, since you already know how to do this:
By multiplying the columns and then adding the results, the answer is 27893.
Notice that the column headings are all 2 raised to a power, formula_1, formula_2, formula_3, formula_4, and so on. To convert from hexadecimal to denary, we must use column headings that are powers with the base 16, like this:
formula_5
formula_6 (You should memorize the values A-F)
formula_7
formula_8
Totalling them all up gives us 27893, showing that 0110110011110101 is equal to 6CF5.
To convert from denary to hexadecimal, it is recommended to just convert the number to binary first, and then use the simple method above to convert from binary to hexadecimal.
Negative Binary Numbers.
A computer works purely in binary. That means that it only uses ones and zeros, and there's no - or + symbol that the computer can use. The computer must represent negative numbers in a different way.
Twos Complement.
We can represent a negative number in binary by making the most significant bit a sign bit, which will tell us whether the number is positive or negative. The column headings for an 8 bit number will look like this:
Here, the most significant bit is negative, and the other bits are positive. You start with -128, and add the other bits as normal. The example above is -67 in denary. -1 in binary is 11111111.
Note that you only use the most significant bit as a sign bit if the number is specified as signed. If the number is unsigned, then the msb is positive.
Converting Negative Numbers.
To find out the value of a two's complement number we must first make note of its sign bit (the most significant, left most bit). If 0 then the number is positive, if 1 then the number is negative.
 0000 0101 (positive)
 1111 1011 (negative)
To find the value of the negative number we must find and keep the right most 1 and all bits to its right, and then flip everything to its left. Here is an example:
 1111 1011 find the right most one
 1111 1011 
 0000 0101 flip all the bits to its left
We can now work out the value of this new number which is:
 128 64 32 16 8 4 2 1 
 0 0 0 0 0 1 0 1
 4 + 1 = −5 (remember the sign you worked out earlier!)
How about a more complex example?
 1111 1100 find the right most one
 1111 1100
 0000 0100 flip all the bits to its left
 128 64 32 16 8 4 2 1 
 0 0 0 0 0 1 0 0
 4 = −4 (remember the sign you worked out earlier!)
So we know how to work out the value of a negative number that has been given to us. How do we go about working out the negative version of a positive number? Like this, that's how...
Take the binary version of the positive number
 0000 0101 (5)
 0000 0101 find the right most one
 0000 0101 
 1111 1011 flip all the bits to its left
So now we can see the difference between a positive and a negative number
 0000 0101 (5)
 1111 1011 (−5)
Binary Subtraction.
When it comes to subtracting one number from another in binary things can get very messy.
 X (82 denary) 0101 0010
 Y (78 denary) 0100 1110 −
An easier way to subtract Y from X is to "add" the negative value of Y to the value of X
 X−Y = X+(−Y)
To do this we first need to find the negative value of Y
 0100 1110 find the right most one
 0100 1110 
 1011 0010 flip all the bits to its left
Now try the sum again
 0101 0010 X( 82 denary) 
 1011 0010 + Y(−78 denary)
 0000 0100
 (¹)¹¹¹ ¹ the one carried over the bit 9 is ignored
Which comes out as
 128 64 32 16 8 4 2 1 
 0 0 0 0 0 1 0 0
 4 = 4 = 82-78
Binary Fractions.
Up until now, we have only been working with whole numbers, or integers. We need a way to store real numbers on a computer system.
Fixed Point Numbers.
First, we should have a look at one of the ways that we can represent fractions in denary:
As you can see, the column headings have been extended to formula_9 and formula_10. We can do the same thing in binary with the column headings formula_11, formula_12, and so on. The number 12.75 in binary is therefore:
Notice that for the same number of bits after the point, the binary number is less accurate. It can only take 4 different values, whereas the denary number can have 100 different divisions with two digits.
Floating Point Numbers.
If you study other subjects such as Physics or Chemistry, you may come across Floating Point numbers like this
 formula_13 (Planck's constant)
The first bit defines the non-zero part of the number and is called the Mantissa, the second part defines how many positions we want to move the decinal point, this is known as the Exponent and can be positive when moving the decimal point to the right and negative when moving to the left.
formula_14
If you wanted to write out that number in full you would have to move the decimal point in the exponent 34 places to the left, resulting in:
 formula_15
Which would take a lot of time to write and is very hard for the human eye to see how many zeros there are. There for, when we can accept a certain level of accuracy (6.63 = 3 significant figures), we can store a many digit number like planks constant in a small number of digits. You are always weighing up the scope (or range) of the number against its accuracy (number of significant bits).
The same is true with binary numbers and is even more important. When you are dealing with numbers and their computational representation you must always be aware of how much space the numbers will take up in memory. As we saw with the above example, the non floating point representation of a number can take up an unfeasible number of digits, imagine how many digits you would need to store.
formula_15 in binary? (don't worry this question is rhetorical)
A binary floating point number may consist of 2, 3 or 4 bytes, however the only ones you need to worry about are the 2 byte (16 bit) variety. The first 10 bits are the Mantissa, the last 6 bits are the exponent.
formula_17
Just like the denary floating point representation, a binary floating point number will have a mantissa and an exponent, though as you are dealing with binary (base 2) you must remember that that instead of having formula_18 you will have to use formula_19
Fixed point binary allows a computer to hold fractions but due to its nature is very limited in its scope. Even using 4 bytes to hold each number, with 8 bits for the fractional part after the point, the largest number that can be held is just over 8 million. Another format is needed for holding very large numbers.
In decimal, very large numbers can be shown with a mantissa and an exponent. i.e. 0.12² Here the 0.12 is the mantissa and the ² is the exponent. the mantissa holds the main digits and the exponents defines where the decimal point should be placed.
The same technique can be used for binary numbers. For example two bytes could be split so that 10 bits are used for the mantissa and the remaining 6 for the exponent. This allows a much greater scope of numbers to be used.
There are several stages to take when working out a floating point number in binary. In fact it is much like a disco dance routine - known on this page as the Noorgat Dance, Kemp variation (but you wont be tested on name but it should help you to remember)
Lets try it out. We are given the following 16 bit floating point number, with 10 bits for the mantissa, and 6 bits for the exponent. Remember the decimal point is between the first and second most significant bits
 formula_20
 formula_21
The first action we need to perform is the sign, find out the sign of the exponent
 formula_22
 It is 0 so the mantissa is positive
The second step in the Noorgat dance is the slide, we need to find the value of the exponent, that is the last 6 bits of the number
 formula_23
 formula_24
 So we know that the exponent is of size positive one and we will have to move the decimal point 
 one place to the right.
The third step in the Noorgat dance is the bounce that is moving the decimal point of the Mantissa the number of positions specified by the slide, which was one position to the right. Like so:
 formula_25
 formula_26
The fourth step is the optional flip. Check back to the sign stage and see if the Mantissa is negative. It isn't? Oh well you can skip past this stage then as we only flip the number if the mantissa is negative.
The fifth and final step is the swim. Taking the mantissa on its own we can now work out the value of the floating point number. Start at the centre and label each number to the left formula_27 and so on. The each number on the right formula_28 and so on.
 formula_29
 Voila! the answer is 1
Normalising Numbers.
When dealing with Floating point numbers in binary you must make sure that the first two bits are different. That is:
 formula_30
 formula_31
And most definitely NOT
 formula_32
 formula_33
This is because we must make sure the space we are using is being used the greatest efficiency. For instance if we take a denary floating point number such as
 formula_13 (Planck's constant)
If we were to rewrite it as:
 formula_35 (Planck's constant)
Then you can see the representation takes up an extra 2 characters, the two extra 0's, even though it represents exactly the same number. This may be acceptable when you are not worried about how many characters a number makes up, but in binary and with computers the space that numbers take up is very important, and we need the most efficient representation we can. With a fixed number of bits, a normalised representation of a number will display the number to the greatest accuracy possible. You must make sure that your normalisation does not change the sign of the mantissa. Taking a binary floating point number:
 formula_36
We can see that the number starts with formula_37. We need to change this to formula_30 for it be normalised. To do this we need to move the decimal place one position to the right, and to retain the same number represented by the unnormalised number we need to change the exponent accordingly. With a movement one place right to normalise the number we need to change the exponent to move the decimal point one place left to compensate. Thus negating one from the current exponent.
 formula_39
To make sure you have normalised it correctly, check that
 formula_40
Lets try a more complicated example:
 formula_41
To get the mantissa normalised we need to move the decimal point two places to the right. To maintain the same value as the original floating point number we need to adjust the exponent to be two smaller.
 formula_42
Now check that the new normalised value has the same value as the original.