The Representation of
Integers
We need to use binary
representations for every piece of data. Computers operate on binary values (as
a result of being built from transistors).
There are 3 types of
data we want to represent:
1.
integers
2.
characters
3.
floating point values
Integer Representation
There are different
binary representations for integers. Possible qualities:
1.
positive numbers only
2.
positive and negative
numbers
3.
ease of human
readability
4.
speed of computer
operations
While there are many
representations, and all have been used at various times for various reasons,
the ones surrounded by a * are the representations that we
will use extensively.
1.
* unsigned *
2.
sign magnitude
3.
one's complement
4.
* two's complement *
5.
biased (not commonly
known)
6.
BCD (Binary Coded
Decimal), used mainly by business applications in the 1960s and 70s.
Virtually all modern
computers operate based on 2's complement representation. Why?
1.
hardware for doing the
most common operations is faster (the most common operation is addition)
2.
hardware is simpler (and
therefore faster)
Did you notice that both
reasons for using 2's complement representation are the same? Almost always,
when discussing why something is done the way it is done, the answer is the
same: "because it isfaster."
Prerequisite Material from 252 (Starts Here)
Unsigned Integers
the standard binary
encoding you already know
only 0 and positive
values
range: 0 to (2^n) - 1,
for n bits
example:
4 bits, values 0 to 15
n=4, 2^4 -1 is 15
binary decimal hex binary decimal hex
0000
0 0 1000
8 8
0001
1 1 1001
9 9
0010
2 2 1010
10 a
0011
3 3 1011
11 b
0100
4 4 1100
12 c
0101
5 5 1101
13 d
0110
6 6 1110
14 e
0111
7 7 1111
15 f
Prerequisite Material from 252 (Ends Here)
One's Complement Integers
NOT COVERED IN 354, but you should know it anyway, as it makes
understanding Two's Complement easier!
Historically important,
and we use this representation to get 2's complement integers.
Now, nobody builds
machines that are based on 1's comp. integers. In the past, early computers
built by Semour Cray (while at CDC) were based on 1's comp. integers.
Positive integers use
the same representation as unsigned.
00000 is 0
00111 is 7, etc.
00111 is 7, etc.
Negation (finding an
additive inverse) is done by taking a bitwise complement of the representation.
This operation is also known as taking the one's complement.
COMPLEMENT. INVERT. NOT.
FLIP. NEGATE.
This is a logical operation done on a single bit.
The complement of 1 is 0.
The complement of 0 is 1.
This is a logical operation done on a single bit.
The complement of 1 is 0.
The complement of 0 is 1.
Example:
Find
the representation of -1 in 1's complement
representation
for +1: 00001
complement
each bit: 11110
That is -1.
Don't add or remove any bits.
Example:
What decimal value is represented by 11100 ?
This must be a negative number.
To find out which, find the additive inverse!
00011 is
+3 by sight, so 11100 must be -3
Things to notice:
1.
any negative number will
have a 1 in the MSB
2.
there are 2
representations for 0: 00000 and 11111
Prerequisite Material from 252 (Starts Here)
Two's Complement integers
A variation on 1's
complement that does not have two representations for 0. This makes the
hardware that does arithmetic (addition, really) faster than for the other
representations.
a 3-bit example:
bit
pattern: 100 101 110 111
000 001 010
011
1's
comp: -3 -2
-1 0 0
1 2 3
2's
comp.: -4 -3
-2 -1 0
1 2 3
The negative values are
all "slid" down by one, eliminating the extra zero representation.
How to get an integer in
2's comp. representation:
- positive values are the same as for sign mag. and 1's
comp.
they will have a 0 in the MSB (but it is NOT a sign bit!) - positive: just write down the value as before
- negative:
·
use the positive
value 00101 (+5)
·
·
take the 1's comp. 11010 (-5 in 1's comp)
·
add 1 + 1
·
------
·
11011 (-5 in 2's comp)
·
To get the additive
inverse of a 2's complement integer,
1.
take the one's
complement
2.
add 1
This 2-step operation
that results in finding the additive inverse of a two's complement
representation is also known as taking the two's complement.
To add 1
without really knowing how to add:
start
at LSB, for each bit (working right to left)
while the bit is a 1, change it to a 0.
when
a 0 is encountered, change it to a 1 and stop.
All
other remaining bits are the same as before.
Example:
What decimal value does the two's complement 110011 represent?
It must be a negative number, since the most significant bit (msb) is a 1. Therefore, find the additive inverse:
What decimal value does the two's complement 110011 represent?
It must be a negative number, since the most significant bit (msb) is a 1. Therefore, find the additive inverse:
110011
(2's comp. ?)
001100
(after taking the 1's complement)
+
1
------
001101
(2's comp. +13)
Therefore, its additive inverse (110011)
must be -13.
A little bit on Adding
We'll see how to really
do this later, but here's a brief overview.
carry
in a
b sum carry out
0
0 0 0
0
0
0 1 1
0
0
1 0 1
0
0 1
1 0 1
1
0 0 1
0
1
0 1 0
1
1
1 0 0
1
1
1 1 1
1
a 0011
+b +0001
-- -----
sum 0100
It is really just like
we do for decimal!
0 + 0 = 0
1 + 0 = 1
1 + 1 = 2 which is 10 in binary, sum is 0 and carry the 1.
1 + 1 + 1 = 3 sum is 1, and carry a 1.
0 + 0 = 0
1 + 0 = 1
1 + 1 = 2 which is 10 in binary, sum is 0 and carry the 1.
1 + 1 + 1 = 3 sum is 1, and carry a 1.
Prerequisite Material from 252 (Ends Here)
A Convenient Diagram
This diagram is a
standard one that is used to point out the differences between a bit pattern (a
representation), and the values represented by the bit pattern. This version of
the number wheel gives all possibilities of 4-bit representations. For each
representation, it also gives (in the outer circles) the decimal value
represented by the bit pattern. Notice that positive two's complement values
are exactly the same as the unsigned values. It is the bit patterns that have a
1 in the most significant bit position where the values represented differ.
Prerequisite Material from 252 (Starts Here)
Sign Extension
How to change an integer
with a smaller number of bits into the same integer (same representation) with
a larger number of bits.
This is commonly done on
some architectures, so it is best to go over it.
By representation:
- unsigned
·
xxxxx
becomes 000xxxxx
Copy
the original integer into the LSBs, and put 0's elsewhere
- 1's and 2's complement. Called sign extension.
Copy the original integer into the LSBs, take the MSB of original integer and replicate it elsewhere.
Example:
0010101 -> 000 0010101
^ ^^^
11110000 -> 11111111 11110000
^ ^^^^^^^^
Prerequisite Material from 252 (Ends Here)
Overflow
Sometimes a value cannot
be represented in the limited number of bits allowed. Examples:
unsigned, 3 bits: 8 would
require at least 4 bits (1000)
2's comp.,
4 bits: 8 would require at least 5 bits
(01000)
When a value cannot be
represented in the number of bits allowed, we say that overflow has
occurred. Overflow occurs when doing arithmetic operations.
example: 3-bit unsigned
representation
011 (3)
+ 110 (6)
---------
?
(9) it would require 4 bits
(1001) to represent
the value 9 in unsigned rep.
Saya akan memberikan sedikit materi:
Saya akan memberikan sedikit materi:
https://www.google.com/search?q=integer+representation&newwindow=1&biw=1366&bih=667&source=lnms&tbm=isch&sa=X&ei=k0FWVJGYJNCouwTn9oLQAQ&ved=0CAgQ_AUoAQ
Tidak ada komentar:
Posting Komentar