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

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:

-128	64	32	16	8	4	2	1
MSB							LSB
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 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:

10	1
1	2	.	7	5

As you can see, the column headings have been extended to  and . We can do the same thing in binary with the column headings , , 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:

8	4	2	1
1	1	0	0	.	1	1	0	0

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

8	4	2	1
0	1	1	0	.	0	0	1	0

This seems simple enough as 6.125 = 4 + 2 + 0.125, but what about this more interesting number: 6.4

8	4	2	1
0	1	1	0	.	0	1	1	0

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  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.

• 

  rotating left logically
 
• 

  rotating right logically

• Arithmetic Shift

You maintain the sign bit of the number being shifted.

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

• 

  Circular rotation left
 
• 

  Circular rotation right

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