Transcript Twos complement notes (PPTX)

COMP 40: Machine Structure
and
Assembly Language Programming (Fall 2014)
Representing Negative Numbers
Noah Mendelsohn
Tufts University
Email: [email protected]
Web: http://www.cs.tufts.edu/~noah
Goals for this presentation
 Discuss the representation of variables that can take
negative or positive values (or zero, of course!)
 Develop your intuition about why 2’s complement
arithmetic works
2
© 2010 Noah Mendelsohn
Representing Negative Numbers
© 2010 Noah Mendelsohn
Bits mean nothing on their own…
 What's this: 1111 0100 ?
 Ideas?
–
–
–
–
–
–
Positive integer 244
HALT instruction (CPU idle)
Negative integer -12
Small o with hat (circumflex)
0.957 pixel brightness (scaled by 255)
bit vector
 With 8 bits we can distinguish 256 choices
– If we use some bit patterns for negative numbers…
– …then those same patterns can no longer stand for positives!
Question…what’s the best representation for negative numbers?
4
© 2010 Noah Mendelsohn
At least three ways to represent negative numbers
We usually represent the number 5 as 0000 0101
How should we represent -5?
 Use the high order bit as a sign (sign and magnitude)
– 1000 0101
 Flip all the bits for negative (ones’ complement)
– 1111 1010
 Flip all bits then add one (two’s complement)
– 1111 1011
5
© 2010 Noah Mendelsohn
These
seem obvious
and
simple…
For example, both
representations have
At least
three
ways
to
represent
negative
numbers
…but there are problems
We usually represent the
separate representations of +0 and -0,
which makes it hard to implement
number
5 as 0000 0101
sequences like:
x = (-3); x = x + 5;
How should we represent -5?
 Use the high order bit as a sign (sign and magnitude)
– 1000 0101
 Flip all the bits for negative (ones’ complement)
– 1111 0101
 Flip all bits then add one (two’s complement)
– 1111 1011
6
© 2010 Noah Mendelsohn
At least three ways to represent negative numbers
We usually represent the Two’s
number
5 as 0000
0101
complement
is trickier
to learn…
but it doesn’t have these problems.
How should we represent…-5?
In fact, two’s complement has many
and almost
modern
advantages,
Use the high
orderallbit
as a sign
computers use it!
(sign and magnitude)
– 1000 0101
 Flip all the bits for negative (ones’ complement)
– 1111 0101
 Flip all bits then add one (two’s complement)
– 1111 1011
7
© 2010 Noah Mendelsohn
Odometer Arithmetic
Modular Number Systems
© 2010 Noah Mendelsohn
The problem:
 I get why:
2 is encoded as 00000010
 I have no clue why:
-2 is encoded as 11111110
9
© 2010 Noah Mendelsohn
Modular arithmetic
What happens when this goes past 999999?
999999 + 1 = 0
So, what should 0 - 1 be?
10
© 2010 Noah Mendelsohn
Modular arithmetic – mod 100
98
99
0
1
2
75
50
11
© 2010 Noah Mendelsohn
Modular arithmetic – mod 256
255 0
1
254
2
192
128
12
© 2010 Noah Mendelsohn
Unsigned modular arithmetic – mod 256
00000000
255 0
1 00000001
11111110 254
2 00000010
11111111
11000000 192
128
10000000
13
© 2010 Noah Mendelsohn
Signed modular arithmetic – mod 256
11111111
11111110 -2
-1
00000000
00000001
0
1
2 00000010
11000000 -64
127 01111111
-128
10000000
14
© 2010 Noah Mendelsohn
The 2s complement magic
127 01111111
The hardware does the same thing, only the interpretatation is different!
15
© 2010 Noah Mendelsohn
Polynomials
© 2010 Noah Mendelsohn
Binary numbers encode coefficients of polynomials
00000101
0 x 2 7 + 0 x 26 + 0 x 2 5 + 0 x 24 + 0 x 24 + 1 x 22 + 0 x 21 + 1 x 20 =
17
5
© 2010 Noah Mendelsohn
Two’s complement numbers as polynomial coefficients
Hi order digit subtracted, all others added!
11111011
-1 x 27 + 1 x 26 + 1 x 25 + 1 x 24 + 1 x 23 + 0 x 22 + 1 x 21 + 1 x 20 =
-128 + 64 + 32 + 16 + 8 + 0 + 2 + 1 =
18
-5
-5
© 2010 Noah Mendelsohn
Try it with -2 in two’s complement
11111110
-128 + 126 = -2
19
© 2010 Noah Mendelsohn
Summary
© 2010 Noah Mendelsohn
Summary
 The bits don’t mean anything by themselves
 Our aritmetic types (unsigned int, signed int) give them an
interpretation
 Almost all modern computers use 2’s complement to
represent signed numbers
– Same hardware arithmetic as unsigned, i.e. mod(MAXINT)
– Avoids problems with duplicate zeros
 You need to learn how 2s complement works, and to
recognize simple values:
– -1, -2, etc.
– Negative number with highest absolute value (e.g. 1000000000000000)
21
© 2010 Noah Mendelsohn