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

Hexadecimal

Questions

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:

Hexadecimal	Binary	Denary
0	0000	0
1	0001	1
2	0010	2
3	0011	3
4	0100	4
5	0101	5
6	0110	6
7	0111	7
8	1000	8
9	1001	9
A	1010	10
B	1011	11
C	1100	12
D	1101	13
E	1110	14
F	1111	15
10	10000	16

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:

32768	16384	8192	4096	2048	1024	512	256	128	64	32	16	8	4	2	1
0	1	1	0	1	1	0	0	1	1	1	1	0	1	0	1

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, $1=2^{0}$ , $2=2^{1}$ , $4=2^{2}$ , $8=2^{3}$ , and so on. To convert from hexadecimal to denary, we must use column headings that are powers with the base 16, like this:

$16^{3}=$ 4096	$16^{2}=$ 256	$16^{1}=$ 16	$16^{0}=$ 1
6	C	F	5

$5\times 1=5$

$15\times 16=240$ (You should memorize the values A-F)

$12\times 256=3072$

$6\times 4096=24576$

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.

NOTE: Hexadecimal is used as it is easier for people to understand than pure binary. It DOES NOT take up less space in memory, only on paper!

Negative Binary Numbers

Questions

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:

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

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

Questions

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:

10	1		${\frac {1}{10}}$	${\frac {1}{100}}$
1	2	.	7	5

As you can see, the column headings have been extended to $10^{-1}={\frac {1}{10}}$ and $10^{-2}={\frac {1}{100}}$ . We can do the same thing in binary with the column headings $2^{-1}={\frac {1}{2}}$ , $2^{-2}={\frac {1}{4}}$ , and so on. The number 12.75 in binary is therefore:

8	4	2	1		${\frac {1}{2}}$	${\frac {1}{4}}$
1	1	0	0	.	1	1

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

  $6.63_{10}\times 10^{-34}$  (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. ${\begin{matrix}\underbrace {6.63} \\Mantissa\end{matrix}}\times {\begin{matrix}\underbrace {10^{-34}} \\Exponent\end{matrix}}$

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:

 $0.00\;000\;000\;000\;000\;000\;000\;000\;000\;000\;000\;663_{10}$

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. $0.00\;000\;000\;000\;000\;000\;000\;000\;000\;000\;000\;663_{10}$ 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.

$\underbrace {\overbrace {0} ^{\text{sign bit}}\cdot 101010101} _{\text{mantissa}}\times \underbrace {010101} _{\text{exponent}}$

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 $\times 10^{xy}$ you will have to use $\times 2^{xy}$

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)

Sign - find the sign of the mantissa (make a note of this)
Slide - find the value of the exponent and whether it is positive or negative
Bounce - move the decimal the distance the exponent asks, left for a negative exponent, right for a positive
Flip - If the mantissa is negative perform twos complement on it
Swim - starting at the decimal point work out the values of the mantissa. Now make sure you refer back to the sign you recorded on the sign move.

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

 $0100\;0000\;0000\;0001$ 
 $0.100\;0000\;00\;\mid \;00\;0001$

The first action we need to perform is the sign, find out the sign of the exponent

 ${\underline {0}}.100\;0000\;00\;\mid \;00\;0001$ 
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

 $0.100\;0000\;00\;\mid \;{\underline {00\;0001}}$

 ${\begin{matrix}32&16&8&4&2&1\\0&0&0&0&0&1\end{matrix}}=1$ 
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:

 $0.{\vec {1}}00\;0000\;00\;\mid \;00\;0001$ 
 $01.00\;0000\;00\;\mid \;00\;0001$

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 $1,2,4,8,16$ and so on. The each number on the right ${\frac {1}{2}}{\frac {1}{4}}{\frac {1}{8}}{\frac {1}{16}}$ and so on.

 ${\begin{matrix}4&2&1&.&{\frac {1}{2}}&{\frac {1}{4}}&{\frac {1}{8}}\\0&0&1&.&0&0&0\end{matrix}}=1=0.100\;0000\;00\;\mid \;00\;0001$ 

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:

 $0.1$ 
 $1.0$

And most definitely NOT

 $1.1$ 
 $0.0$

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

  $6.63_{10}\times 10^{-34}$  (Planck's constant)

If we were to rewrite it as:

  $0.0663_{10}\times 10^{-32}$  (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:

 $0.010\;0000\;00\;\mid \;00\;0011$

We can see that the number starts with $0.01$ . We need to change this to $0.1$ 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.

 $0.010\;0000\;00\;\mid \;00\;0010$

To make sure you have normalised it correctly, check that

 $0.010\;0000\;00\;\mid \;00\;0010=0.100\;0000\;00\;\mid \;00\;0011$

Lets try a more complicated example:

 $1.110\;0000\;00\;\mid \;11\;1110$

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.

 $1.000\;0000\;00\;\mid \;11\;1100$

Now check that the new normalised value has the same value as the original.