Number Representations
Download
Report
Transcript Number Representations
Number Representations and
Computer Arithmetic
“Computing” with Computers
Back in the “old days”
(WW II time), the
word “computer”
meant this
• “Computers” were used
to compute things such
as trajectory tables,
etc.
– redundant “computers”
for reliability and speed
• Quite effective!
CS 21a
9/23/02
– new computers were tested
against human computers
© Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Odds and Ends
Slide 2
“Computing” with Computers
Of course, we don’t do things
that way anymore!
But HOW do (electronic)
computers compute?
The trick is to use BINARY
numbers
CS 21a
9/23/02
use 1’s and 0’s
corresponds on current/voltage
being ON or OFF
easy to implement
resilient against noise
© Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Odds and Ends
Slide 3
Java types: int and double
int range:
-2,147,483,648 to 2,147,483,647
double range:
4.94e-324 to 1.80e+308
These ranges depend on:
CS 21a
9/23/02
Storage size
Internal data representation
© Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Odds and Ends
Slide 4
Review: Decimal Numbers
Integer Representation
number is sum of DIGIT * “place value”
d7 d6 d5 d4 d3 d2 d1 d0
Range
0 to 10n - 1
107 106 105 104 103 102 101 100
379210 = 3 103 + 7 102 + 9
= 3000 + 700 + 90 + 2
101
+ 2
100
Adding two decimal numbers
add by “place value”, one digit at a time
3792
+ 531
???
CS 21a
9/23/02
0 0 0 0 3 7 9 2
1
3 7 9 2
+ 0 5 3 1
0 4 3 2 3
“carry 1”
because
9+3 = 12
© Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Odds and Ends
Slide 5
Binary Numbers
• Humans can naturally count up to 10 values,
• But computers can count only up to 2 values
(OFF and ON, or 0 and 1)
(Unsigned) Binary Integer Representation
“base” of place values is 2, not 10
b7 b6 b5 b4 b3 b2 b1 b0
Range
0 to 2n - 1
CS 21a
9/23/02
0 1 1 0 0 1 0 0
27 26 25 24 23 22 21 20
011001002 = 26 + 25 +
22
= 64 + 32 + 4
aka “0b01100100”
= 10010
© Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Odds and Ends
Slide 6
Converting from Binary to Decimal
VERY USEFUL trick for a CS/MIS person …
Memorize powers of 2 from 20 up to 210
Lets you approximate any power of 2
Example 1: what is 216?
“1 KB” is actually 1,024 bytes, not 1000 bytes
“1 MB” is 1K*1KB = 220 bytes
= 1,048,576 bytes
= approximately 1 million bytes
“1 GB” is 1K * 1MB = 230 bytes = (approx 1 billion)
26 * 210 = 64 * 1024 = 64 K = 65,536
Example 2:
CS 21a
9/23/02
20
21
22
23
24
25
26
27
28
29
210
=
=
=
=
=
=
=
=
=
=
=
1
2
4
8
16
32
64
128
256
512
1,024
or “1K”
The Pentium processor does integer math
with 32-bit numbers. What’s the highest
unsigned number it can handle (approximately)?
range = 2n-1 = 232 - 1
232 = 22 * 230
= 4 * 1 G = approximately 4 billion
= actually 4*1024*1024*1024 = 4,294,967,296 (minus 1)
© Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Odds and Ends
Slide 7
Converting from Binary to Decimal
More practice
0b00000010
0b00001110
0b00110001
0b10110001
CS 21a
9/23/02
© Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
20
21
22
23
24
25
26
27
28
29
210
=
=
=
=
=
=
=
=
=
=
=
1
2
4
8
16
32
64
128
256
512
1,024
or “1K”
Odds and Ends
Slide 8
From Decimal to Binary
General rule:
Divide and write remainder
from right to left
Why this works
remainder gives bit 0
odd numbers have a 1 in bit 0
Note that this rule works in
converting decimal to any base
e.g., HEX numbers (more later)
3792 / 2 = 1896 rem 0
1896 / 2 = 948 rem 0
948 / 2 = 474 rem 0
474 / 2 = 237 rem 0
237 / 2 = 118 rem 1
118 / 2 =
59 rem 0
59 / 2 =
29 rem 1
29 / 2 =
14 rem 1
14 / 2 =
7 rem 0
7 / 2 =
3 rem 1
3 / 2 =
1 rem 1
1 / 2 =
0 rem 1
0b111011010000
= 211+210+29+27+26+24
= 3792
CS 21a
9/23/02
© Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Odds and Ends
Slide 9
Binary Arithmetic
Adding two decimal numbers
3792
+ 531
???
0 4 3 2 3
“carry 1”
because
9+3 = 12
Adding two binary numbers
CS 21a
9/23/02
1
3 7 9 2
+ 0 5 3 1
same, but “1 + 1 = 10”
14
+ 7
1 1 1
1 1 1 0
+ 0 1 1 1
21
1 0 1 0 1
“carry 1”
because
1+1 = 10
© Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Odds and Ends
Slide 10
Binary Arithmetic
In general:
Add up to 3 bits at a time
per place value
1 1 1 0 0
1 1 1 0
+ 0 1 1 1
sum bits
carry-out bits
0 1 0 1
1 1 1 1 0
Output 2 bits at a time
CS 21a
9/23/02
A and B
“carry in”
carry-in bits
A bits
B bits
sum bit for that place value
“carry out” bit
(becomes carry-in
of next bit)
© Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Odds and Ends
Slide 11
So what about negative values?
In math, it is easy to represent negative values
Just put a negative sign (-) prefix
In computers, we extend the binary notation in
order to support signed values
We can use the following 3 methods:
CS 21a
9/23/02
Sign and magnitude (using the Most Significant Bit
or MSB)
1’s complement
2’s complement
© Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Odds and Ends
Slide 12
Signed Integers
Sign-and-Magnitude
210
-210
0 010
1 010
010
-010
0 000
1 000
flip bits
easy to do subtraction
STILL has 2 “zeros”
210
-210
0 010
1 101
010
-010
0 000
1 111
210
-210
0 010
1 110
010
-010
0 000
0 000
1’s complement
MSB represents sign bit (0 for
positive, 1 for negative)
has 2 “zeroes”
2’s complement
flip bits, then add 1
easy subtraction
(just negate, then add)
has only 1 zero
Another interpretation:
CS 21a
9/23/02
add place values as before,
except that MSB is negative
n-1)John Paul Vergara,
(i.e., MSB©isLuis
place
is 2and
F. G.value
Sarmenta
Ateneo de Manila University
Odds and Ends
Slide 13
Binary Subtraction
1’s complement subtraction: flip the negative
5 - 3 = 2
0 1 0 1
0101
0011 flip
1100
-3 in 1’s complement form
3 - 5 = -2
0011
0101 flip
1010
+1 1 0 0
1 0 0 0 1
1
0 0 1 0
Add the
carry
overflow
2
0 0 1 1
+1 0 1 0
1 1 0 1
-2
-5 in 1’s complement form
CS 21a
9/23/02
© Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Odds and Ends
Slide 14
Binary Subtraction
2’s complement subtraction: flip then add 1
5 - 3 = 2
0101
0011 flip
1100 +1
1101
-3 in 2’s complement form
3 - 5 = -2
0011
0101 flip
1010 +1
1011
-5 in 2’s complement form
CS 21a
9/23/02
0 1 0 1
+1 1 0 1
1 0 0 1 0
2
ignore
overflow
0 0 1 1
+1 0 1 1
1 1 1 0
0001 flip
0010 +1
-2
(flip+1 also gives positive of negative number)
© Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Odds and Ends
Slide 15
Range of binary numbers
Java (and most computer platforms
today) use 2’s comp.
Hence the range for the different int
types
byte (8 bits): ?
short (16 bits): ?
int (32 bits): -2,147,483,648 to
2,147,483,647
long (64 bits): ?
CS 21a
9/23/02
© Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Odds and Ends
Slide 16
Hexadecimal (Hex) Numbers
aka “0x64”
Base 16
Each hex digit goes
6416 = 6*1610 + 4 =
from 0-9, then A-F
Hex is a convenient
shortform for binary
b7 b6 b5 b4 b3 b2 b1
4 bits = 1 hex digit
0 1 1 0 0 1 0
(aka nibble)
27 2 6 25 24 23 22 21
1 byte = 8 bits = 2 hex digits
Another useful trick:
b0
0
20
memorize binary of 0 to F
Addition and conversion
to/from decimal is similar
CS 21a
9/23/02
10010
except use base 16 instead of 2
© Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Odds and Ends
Slide 17
Some Exercises
What’s the range of an n-bit sign-mag integer?
How about 1’s comp? 2’s comp?
Convert the ff signed 8-bit values to decimal
Convert the ff to 16-bit binary and hex numbers:
CS 21a
9/23/02
413, 39, 1045, -3, -124, -134
Add the following pairs
0b01010101, 0b1110111, 0x14, 0x41
0b00001011 + 0b00100100, 0x3F + 0x2F
If 0x7F and 0x32 are signed 8-bit integers, what’s
wrong with adding them and storing the result in a
byte?
Puzzle: How can I use my 10 fingers to count up to
1000?
© Luis F. G. Sarmenta and John Paul Vergara,
Ateneo de Manila University
Odds and Ends
Slide 18