Sunday, May 19, 2013

Binary Over Flow


Maths in a processor is normally performed using set numbers of bits. For example where you add 8 bits to 8 bits. This will often cause no problems at all:
 00110011 (51)
+00001010 (10)
 --------
 00111101 (61)
But what happens if we add the following numbers together:
 01110011 (115)
+01001010 (74)
 --------
 10111101 (189)
This may appear to have gone ok, but we have a problem. If we are dealing with twos complement numbers the answer from adding two positive numbers together is negative!
 01110011 (115)
+01001010 (74)
 --------
 10111101 (-67!)

Binary Substraction

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 (82 denary)
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
Exercise: Binary subtraction
Find the answers to the following sums in binary, show your working
  0110 1100 (108)
- 0000 0111 (7)

Answer :
Convert the 0000 0111 into a negative number 1111 1001 = -7 Add both numbers together:
   0110 1100
 + 1111 1001
   0110 0101 = 101
(¹)¹¹¹¹         the one carried over the bit 9 is ignored
  0001 1111 (31)
- 0001 0011 (19)
  
Answer :
Convert the 0001 0011 into a negative number 1110 1101 = -19 Add both numbers together:
   0001 1111
 + 1110 1101
   0000 1100 = 12
(¹)¹¹¹¹ ¹¹¹    the one carried over the bit 9 is ignored
  0111 0111 (119)
- 0101 1011 (91)
  
Answer :
Convert the 0101 1011 into a negative number 1010 0101 = -91 Add both numbers together:
   0111 0111
 + 1010 0101
   0001 1100 = 28
(¹)¹¹   ¹¹¹    the one carried over the bit 9 is ignored
23 (hex)  - 1F (hex)

Answer :
Convert the HEX values to binary
0010 0011 = 23 HEX or 35 denary
0001 1111 = 1F HEX or 31 denary
Now let's find the negative value of 1F
1110 0001 = -31
Add both numbers together:
   0010 0011
 + 1110 0001
   0000 0100 = 4
(¹)¹¹¹   ¹¹    the one carried over the bit 9 is ignored
  0001 0010 (10)
- 1111 1101 (-31)
  
Answer :
They have tried to trick you. What is the a number minus a negative number? X - (-Y) = X + Y
Let's start by finding the value of the bottom number: 1110 0001 -> 0001 1111 = -31
And by working this out we have the positive value (0001 1111) Add both numbers together:
   0001 0010 (18)
 + 0001 1111 (31)
   0011 0001 = 49
(¹)  ¹

Signed and Unsigned binary numbers - twos complement


We can represent a negative number in binary by making the most significant bit (MSB) 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:
-1286432168421
MSBLSB
10111101
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 because: (-128 + 32 + 16 + 8 + 4 + 1 = -67)
-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 regardless of whether it is a one or not.
Signed binary numbers
If the MSB is 0 then the number is positive, if 1 then the number is negative.
0000 0101 (positive)
1111 1011 (negative)

Converting Negative Numbers

To find out the value of a twos complement number we must first make note of its sign bit (the most significant, left most bit), if the bit is a zero we work out the number as usual, if it's a one we are dealing with a negative number and need to find out its value.
Method 1: converting twos complement to denary
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 note the number is negative
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!)
Method 2: converting twos complement to denary
To find the value of the negative number we must take the MSB and apply a negative value to it. Then we can add all the heading values together
1111 1011 note the number is negative
-128  64  32  16   8   4   2   1 
   1   1   1   1   1   0   1   1
-128 +64 +32 +16  +8      +2  +1 = -5
How about a more complex example?
Method 1: converting twos complement to denary
1111 1100 note the number is negative 

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!)
Method 2: converting twos complement to denary
To find the value of the negative number we must take the MSB and apply a negative value to it. Then we can add all the heading values together
1111 1100 note the number is negative
-128  64  32  16   8   4   2   1 
   1   1   1   1   1   1   0   0
-128 +64 +32 +16  +8  +4          = -4
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...
Method 1: converting twos complement to binary
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)
Method 2: converting twos complement to binary
Take the binary version of the positive number
starting with -128, we know the MSB is worth -128. We need to work back from this:
-128  64  32  16   8   4   2   1 
   1   1   1   1   1   0   1   0   
-128 +64 +32 +16  +8      +1      = -5
0000 0101 (5)
1111 1011 (−5)
Exercise: two's complement numbers
Convert the following two's complement numbers into denary:

0001 1011
 
Answer :
(positive number) 27

1111 1111
Answer :
(negative number) 0000 0001 = -1


0111 1101
Answer :
(positive number) 125

1001 1001
Answer :
(negative number) 0110 0111 = -103
1011 1000

 
Answer :
(negative number) 0100 1000 = -72

81 (hexadecimal)
Answer :
(using 4 bits for each HEX char) 1000 0001
(negative number) -> 0111 1111 = -127

A8 (hexadecimal)
Answer :
(using 4 bits for each HEX char) 1010 1000
(negative number) -> 0101 1000 = -88
Convert the following numbers into negative numbers written in binary

0000 0001
Answer :
1111 1111

0110 0000
Answer :
1010 0000

0111 1111
Answer : 
1000 0001

12 (denary)
Answer :
0000 1100 = +12 -> 1111 0100 = -12


67 (denary)
Answer :
0100 0011 = +67 -> 1011 1101 = -67

34
Answer :
0010 0010 = +34 -> 1110 1110 = -34

34 (hexadecimal)
Answer :
(using 4 bits for each HEX char) 0011 0100 = +52 -> 1100 1100 = -54

7E (hexadecimal)
Answer :
(using 4 bits for each HEX char) 0111 1110 = +126 -> 1000 0010 = -126

Binary Fractions

So far we have only looked at whole numbers (integers), we need to understand how computer represent fractions.
You should have learnt at Primary School how a denary fraction works:
101\frac {1}{10}\frac {1}{100}
10^110^010^{-1}10^{-2}
12.75
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 8 bit binary with 4 bits after the decimal point is therefore 8 + 4 + 0.5 + 0.25:
8421\frac {1}{2}\frac {1}{4}\frac {1}{8}\frac {1}{16}
2^32^22^12^02^{-1}2^{-2}2^{-3}2^{-4}
1100.1100
Notice that for the same number of bits after the point, the binary fraction is less accurate. It can only take 4 different values, whereas the denary number can have 100 different divisions with two digits. You'll see in a moment how this can be troublesome.

Converting Binary to Decimal

We are going to convert the number 6.125 into a binary decimal by using the grid below
8421\frac {1}{2}\frac {1}{4}\frac {1}{8}\frac {1}{16}
0110.0010
This seems simple enough as 6.125 = 4 + 2 + 0.125, but what about this more interesting number: 6.4
8421\frac {1}{2}\frac {1}{4}\frac {1}{8}\frac {1}{16}
0110.0110
But this doesn't look right?! This number isn't correct as it only reaches 4 + 2 + 0.25 + 0.125 = 6.375, we need some more bits for the decimal places. However, in a computer you might be restricted to the number of bits you can use, so we'll use the number closest to the one we were aiming for. You feel a bit annoyed at this, but don't worry, you make this compromise every time that you try to represent \frac {1}{3} in denary, or 0.33333333; you see what I mean.
 converting from denary to binary fractions
Now try some questions yourself and see how you get on. Remember, where there aren't enough bits for the decimal place, write down the number closest to your target number. In each case use 8 bits for the binary with four bits after the decimal point:
7.5

Answer :
0111.1000
4.5625

Answer :
0100.1001
1.6
  
Answer :
0001.1001 (this is the closest we are going to get)
3.3333333

Answer :
0011.0101 (this is the closest we are going to get)
Try and convert these binary fractions into denary:
0111.0100

Answer :
7.25
1011.1001
  
Answer :
11.5625 (notice that we treated this as a positive number, some of you might already know about twos complement, if you haven't heard about it before, don't worry, we'll get there very soon)
To interpret it as a two's complement number let's flip it: 0100.0111 = 4 + 0.25 + 0.125 + 0.0625 = -4.4375
If I want to increase the range of numbers stored in a fixed point binary number, what should I do?
  
Answer
Increase the number of bits before the decimal point
If I want to increase the accuracy of numbers stored in a fixed point binary number, what should I do?

Answer :
Increase the number of bits after the decimal point



Bit Shiting

if you look at the binary representations of the following numbers you may notice something peculiar:
0001 = 1
0010 = 2
0100 = 4
1000 = 8
Each time we shift the number one space to the left, the value of the number doubles. This doesn't only work for one bit, take a look at this more complicated example.
0001 0101 = 21
0010 1010 = 42
Again, one shift to the left and the number has doubled. On the other hand, one shift to the right halves the value.
Computers are notoriously bad at doing multiplication and division, it takes lots of CPU time and can really slow your code down. To try and get past this problem computers can shift the values in registers and as long as multiplication or division is by powers of 2, then the CPU time is reduced as the action takes only one line of Machine Code. There are several types of shifts that processors can perform:
  • Logical Shift
Shifting either left or right, you add a 0 on the empty end.
  • Arithmetic Shift
You maintain the sign bit of the number being shifted.
Rotate right arithmetically.svg
Please note the Logical shift example is also an example of an arithmetic shift as the sign remains the same. You'll find out about sign bits when learning about two's complement
  • Circular Shift
The bit that is pushed off one end appears on the other

Binary Multiplication

You should hopefully have learnt how to multiply numbers together in decimal when you were at primary school. Let's recap:
 12
x 4
 --
  8   =  4*2
 40   =  4*10
 --
 48
And with a more complicated example:
 12
x14
 --
  8   =  4 * 2
 40   =  4 * 10
 20   =  10* 2
100   =  10* 10
 --
168
The same principle applies with binary. Let's take a look at an example:
 101
x 10
----
   0   =  0 * 101
1010   = 10 * 101 [or in denary 2 * 5 = 10]
Let's try a more complicated example:
   1011 [11]
  x 111 [7]
  ----
   1011 =   1 * 1011 
  10110 =  10 * 1011
 101100 = 100 * 1011
 ------ now add them together
1001101 = [77 double check with the decimal earlier]

Exersizes

101 * 10

Answer :
 101
x 10
----
1010
11 * 11
Answer :
  11
x 11
----
  11
 110
----
1001
1011 * 101
Answer :
  1011 
x  101
------
  1011
101100
------
110111

1111 * 111
Answer :
    1111  = 15
  x  111  = 7
  ------
    1111
   11110
  111100
  ------
 1101001 = 105
If you multiply a binary number by 2, how many spaces does it move to the left?

Answer :
1
If you multiply a binary number by 16, how many spaces does it move to the left?

Answer :
4 (as 2^4 = 16)
This is a short cut for multiplication in computers, and it uses machine code shift instructions to do this. Don't worry you don'tneed to know them for this syllabus

Binary Addition


Addition [edit]

Let's look at an example of adding in decimal:
 25
+43
---
 68
This is pretty simple, we just add up each column, but what happens if we have can't fit the result in one column. We'll have to use a carry bit:
 98
+57
---
155
11
Hopefully you're good with that. Now let's take a look at how it's done in binary with a very quick example, with a check in denary:
 01010 (1010)
+00101 (510)
------
 01111 (1510)
This seems pretty straight forward, but what happens when we have a carry bit? Well pretty much the same as in denary:
 01011 (1110)
+00001 (110)
------
 01100 (1210)
   11


1010 + 0001
Answer :
 1010
+0001 ----
 1011

01001001 + 00110000
Answer :
 01001001 
+00110000
 --------
 01111001

01010100 + 00110000
Answer :
 01010100 
+00110000
 --------
 10000100

01001010 + 00011011
Answer :
 01001010 
+00011011
 --------
 01100101

01111101 + 00011001
Answer :
 01111101 
+00011001
 --------
 10010110

00011111 + 00011111
Answer :
 00011111 
+00011111
 --------
 00111110

10101010 + 01110000
Answer :
 10101010 
+01110000
 --------
100011010
Note we have some overflow, this will come in useful when doing subtraction