Transcript Sign Extension and Overflow

1
Bits, Data types, and Operations:
Chapter 2
COMP 2610
Dr. James Money
COMP 2610
Addition and Subtraction

We will now use only two’s complement
representation for integers

The arithmetic proceeds as we introduced
before using long addition

At each stage there is a sum digit and a carry
digit
Example

Using 5 bit notation, what is 11+3?

Note
–
(11)10 = (01011)2
–
(3)10 = (00011)2
–
Sum is (01110)2 = (14)10
Subtraction

Recall the definition of subtraction from
algebra:
For all real numbers a, b, we define
subtraction by
a-b = a+(-b)
Negation

How do we form –b?

We take b and form the the two’s
complement of the number

What is the two’s complement form in 5 bit
notation for
–
5
–
-10
Subtraction

What is 14-9?
–
(14)10 = (01110)2
–
(9)10 = (01001)2
–
(-9)10 = (10111)2
–
Thus 14-9 = 14+-9 = (00101)2 = (5)10
Addition of same number

What happens when you add a number to
itself, that is x+x?

Using 8 bits, consider x=(59)10 = (00111011)2

We get x+x=2x = (118)10 = (01110110)2

This is the bits shifted to the left by one!
Addition of same number

Why?

59 = 0x26+1x25+1x24+1x23+0x22+0x21+1x20

So 59+59 = 2 x 59 =
2(0x26+1x25+1x24+1x23+0x22+0x21+1x20)
= 0x27+1x26+1x25+1x24+0x23+0x22+1x21

This is shifting the bits to the left by one
Sign Extension

Many times we represent a number with
fewer bits to save space

For example, (5)10 = (00000000000101)2

And it is the same as (000101)2

For positive numbers, we can zero extend
the bits to the left to get the same number
Sign Extension

How about negative numbers?

For (-5)10 = (111011)2 in 8 bits

In 16 bits, we get
(11111111111011)2

We add leading ones for negative numbers
Sign Extension

+
Suppose we had to add the numbers
0000000000001101
13
111011
-5
Sign Extension

In either case, we extend the bits using SignEXTension, abbreviated SEXT

That is we extend by the correct sign:
–
By 0 if positive
–
By 1 if negative
Overflow

So far we have assumed that the sum of the
two integers is small enough to be
represented in the number of available bits

What happens if this is not the case?

We get a condition known as overflow
Overflow

This situation is analogous to the old
odometers which had only 5 digits

What happens after 99999?

It rolls back to 00000 and looks like a new
car with no miles

The carry of ten-thousands digit is lost
Overflow

For two’s complement arithmetic, this can be
more subtle

Consider 5 bits numbers and add 9+11
01001
+ 01011
10100
Overflow

However, this number is -12!

We say this result has overflowed the
capacity of the representation since we
added to positive numbers and got a
negative one
Overflow

Consider -12+-6:
10100
+ 11010
01110