Transcript Number systems and computer arithmetic

Number Systems and
Computer Arithmetic
Winter 2014
COMP 1380 Discrete Structures I
Computing Science
Thompson Rivers University
Course Contents








Speaking Mathematically
Number Systems and Computer Arithmetic
Logic and Truth Tables
Boolean Algebra and Logic Gates
Vectors and Matrices
Sets and Counting
Probability Theory and Distributions
Statics and Random Variables
TRU-COMP1380
Number Systems
2
Unit Learning Objectives













Convert a decimal number to binary number.
Convert a decimal number to hexadecimal number.
Convert a binary number to decimal number.
Convert a binary number to hexadecimal number.
Convert a hexadecimal number to binary number .
Add two binary numbers.
Compute the 1’s complement of a binary number.
Compute the 2’s complement of a binary number.
Understand the 2’s complement representation for negative integers.
Subtract a binary number by using the 2’s complement addition.
Multiply two binary numbers.
Use of left shift and right shift.
Binary division
TRU-COMP1380
Number Systems
3
Unit Contents
The number systems:

The decimal system

The binary system

The hexadecimal system
Computer Arithmetic:
 Binary addition

Representation of negative integers

Binary multiplication

Binary division

Representation of fractions
TRU-COMP1380
Number Systems
4
1. Number Systems
TRU-COMP1380
Number Systems
5
The Decimal System

Uses 10 digits 0, 1, 2, ..., 9.

Decimal expansion:





83 = 8×10 + 3
4728 = 4×103 + 7×102 + 2×101 + 8×100
84037 = ???
43.087 = ???
Do you know addition, subtraction, multiplication and division?




1234 + 435.78
1234 – 435.78
1234 × 435.78
1234 / 435.78
TRU-COMP1380
Number Systems
6
The Binary System






In computer systems, the most basic memory unit is a bit that contains
0 or 1.
The data unit of 8 bits is referred as a byte that is the basic memory
unit used in main memories and hard disks.
All data are represented by using binary numbers. Data types such as
text, voice, image and video have no meaning in the data
representation.
8 bits are usually used to express English alphabets.
A collection of n bits has 2n possible states(, i.e., numbers). Is it true?
E.g.,




How many different numbers can you express using 2 bits?
How many different numbers can you express using 4 bits?
How many different numbers can you express using 8 bits?
How many different numbers can you express using 32 bits?
TRU-COMP1380
Number Systems
7


How can we store integers (i.e., positive numbers only) in a computer?
E.g.,




A decimal number 329?
Is it okay to store 3 chracters ‘3’, ‘2’, and ‘9’ for 329?
How do we store characters?
32910 = ???2
TRU-COMP1380
Number Systems
8

Uses two digits 0 and 1.


02
12
102
112
1002
1012
1102
1112
10002
10012

...








TRU-COMP1380
=
=
=
=
=
=
=
=
=
=
0×20
1×20
1×21
1×21
1×22
1×22
1×22
1×22
1×23
1×23
=
=
+
+
+
+
+
+
+
+
0×20
1×20
0×21
0×21
1×21
1×21
0×22
0×22
=
=
+
+
+
+
+
+
0×20
1×20
0×20
1×20
0×21
0×21
=
=
=
=
+ 0×20 =
+ 1×20 =
Number Systems
010
110
210
310
410
510
610
710
810
910
9

Powers of 2

12
102
1002
10002
1 00002
10 00002
10 000002






TRU-COMP1380
=
=
=
=
=
=
=
1×20
1×21
1×22
1×23
24 =
25 =
26 =
=
+ 0×20 =
+ 0×21 + 0×20 =
+ 0×22 + 0×21 + 0×20 =
Number Systems
110
210
410
810
1610
3210
6410
10

1000
0000
0000
0000
0000
0000
00002
00002
00002
00002
00002
00002
=
=
=
=
=
=
27 =
28 =
29 =
210 =
211 =
212 =

1
10
100
1000
1 0000

Can you memorize the above powers of 2?

Converting to decimals
11012 = ???10
1011 00102 = ???10
1011.00102 = ???10







TRU-COMP1380
Number Systems
???10
???10
???10
???10
???10
???10
11
Converting Decimal to Binary

23 / 2
11 / 2
5/2
2/2
1/2
=>
2310 = 101112

27110 = ???2
607110 = ???2

TRU-COMP1380
Quotient
11
5
2
1
0
Number Systems
Remainder
1
1
1
0
1
12


Another similar idea
27110 = ???2
256 < 271 < 512
8< 15 < 16
=>
271

-> 271 = 256 + 15
= 1 0000 00002 + 15
-> 15 = 8 + 7
= 10002 + 7
= 1 0000 00002 + 15
= 1 0000 00002 + 10002 + 7
= 1 0000 00002 + 10002 + 1112
= 1 0000 11112
127110 = ???2
TRU-COMP1380
Number Systems
13
Hexadecimal Number System


















010 = 00002 = 016 = 0x0
110 = 00012 = 116 = 0x1
210 = 00102 = 216 = 0x2
310 = 00112 = 316 = 0x3
410 = 01002 = 416 = 0x4
510 = 01012 = 516 = 0x5
610 = 01102 = 616 = 0x6
710 = 01112 = 716 = 0x7
810 = 10002 = 816 = 0x8
910 = 10012 = 916 = 0x9
1010 = 10102 = A16 = 0xA
1110 = 10112 = B16 = 0xB
1210 = 11002 = C16 = 0xC
1310 = 11012 = D16 = 0xD
1410 = 11102 = E16 = 0xE
1510 = 11112 = F16 = 0xF
0x23c9d6ef = ???10
14816 = ???10
TRU-COMP1380
4 bits can be used for a
hexadecimal number, 0, ..., F.
Please memorize it!
0x23c9d6ef = ???2
14816 = ???2
Number Systems
14
Converting Decimal to Hexadecimal
Quotient
20 × 16 +
1 × 16 +
0 × 16 +
Remainder
8
4
1

328 / 16 =
20 / 16 =
1 / 16 =
=>
32810 = 14816 = ???2

14816 = (1 × 162 + 4 × 161 + 8 × 160)10

19210 = ???16
TRU-COMP1380
Number Systems
15
Converting Binary to Hexadecimal

4DA916 = ???2

1001101101010012 = ???16
= 100 1101 1010 1001
= 4DA9

10 11102 = 0x??? = ???10
0100 1110 1011 1001 01002 = 0x??? = ???10

TRU-COMP1380
Number Systems
16
2. Computer Arithmetic
TRU-COMP1380
Number Systems
17
Binary Addition



How to add two binary numbers? Let’s consider only unsigned
integers (i.e., zero or positive numbers only) for a while.
Just like the addition of two decimal numbers.
carry
E.g.,
10010
10010
1111
+
1001
+
1011
+
1
11011
11101
???
+
TRU-COMP1380
10111
111
???
Number Systems
18
Binary Subtraction



How to subtract a binary number?
Just like the subtraction of decimal numbers.
E.g.,
0112
02
02
1000
10
10
10010
10010
-1
-1
-11
-11
1
?1
?11
Try:

101010
-101
How to do?
10010
-11
1111
1
-10
34–79=?
Is subtraction easier or more difficult than addition? Why?
TRU-COMP1380
Number Systems
19






In the previous slide, 10010 – 11 = 1111
What if we add
00010010
+ 11111100
1 00001110
+
1
00001111
Is there any relationship between 112 and 111111002?
The 8-bit 1’s complement of 112 is ??? Switching 0  1
This type of addition is called 1’s complement addition.
Find the 8-bit one’s complements of the followings.



11011 -> 00011011 ->
10 -> 00000010 ->
101 -> 00000101 ->
TRU-COMP1380
Number Systems
20




In the previous slide, 10010 – 11 = 1111
What if we add
00010010
+ 11111101
1 00001111
Is there any relationship between 11 and 11111101?
The 8-bit 2’s complement of 11 is ???



2’s complement ≡ 1’s complement + 1
->
11111100 + 1 = 11111101
This type of addition is called 2’s complement addition.
Find the 16-bit two’s complements of the followings.



11011 -> 0000000000011011 ->
10
101
TRU-COMP1380
Number Systems
21

Another example
-
101010
101
???

What if we use 1’s complement addition or 2’s complement addition
instead as followings? Let’s use 8-bit representation.
1’s complement addition
+
1
+

00101010
11111010
00100100
1
00100101
+
1
00101010
11111011
00100101
2’s complement addition
What does this mean?


A – B = A + (–B), where A and B are positive
Is –B equal to the 1’s complement or the 2’s complement of B?
TRU-COMP1380
Number Systems
22

Can we use 8-bit 1’s complement addition for 12 – 102 = –12 ?
-
1
10
+
00000001
11111101
11111110
<- 8-bit 1’s complement of 10
<- Is this correct?
(Is this 1’s complement of 1?)

Let’s use 8-bit 2’s complement addition for 12 – 102.
00000001
+ 11111110
11111111



<- 2’s complement of 10
<- Correct? (2’s complement of 1?)
12 – 102 = 12 + (–102)
Subtraction can be converted to addition with negative numbers.
Then, how to represent negative binary numbers, i.e., signed integers?
TRU-COMP1380
Number Systems
23
Representation of Negative Binaries



Representation of signed integers
8 or 16 or 32 bits are usually used for integers.
Let’s use 8 bits for examples.






How to represent positive integer 5?


The left most bit (called most significant bit) is used as sign.
When the MSB is 0, positive integers.
When the MSB is 1, negative integers.
The other 7 bits are used for integers.
What signed integers can be described using the 8 bit representation?
00001001
How about -9?



10001001 is really okay?
00001001 (9) + 10001001 (-9) = 10010010 (-18) It is wrong!
We need a different representation for negative integers.
TRU-COMP1380
Number Systems
24

How about -9?




What is the 8-bit 1’s complement of 9?



11110110
00001001 + 11110110
= 11111111
<- 8-bit 1’s complement of 9
<- 9 + 8-bit 1’s complement of 9
<- Is it zero? (1’s complement of 0?)
What is the 2’s complement of 9?



10001001 is really okay?
00001001 (9) + 10001001 (-9) = 10010010 (-18) It is wrong!
We need a different representation for negative integers.
11110111
00001001 + 11110111
= 1 00000000
<- 8-bit 2’s complement of 9
<- 9 + 8-bit 2’s complement of 9
<- It looks more like zero.
2’s complement representation is used for
negative integers.
TRU-COMP1380
Number Systems
25







12 – 102 = 12 + (–102) ???
00000001
+ 11111110
<- 2’s complement of 10, i.e., -102
11111111
<- 2’s complement of 1, i.e., -1 (= 1 – 2)
1010102 – 10011012 = 001010102 + (–010011012) ???
100102 – 112 ???
102 – 1112 ???
–102 – 12 ???
Is the two’s complement of the two’s complement of an integer the
same integer?
What is x when the 8-bit 2’s complement of x is

11111111
TRU-COMP1380
11110011
Number Systems
10000001
26





8-bit representation with 2’s complement
127
01111111
126
01111110
overflow
...
...
2
00000010
1
00000001
0
00000000
-1
11111111 (28 – 1)
-2
11111110
-3
11111101
...
...
-127
10000001
-1
-128
10000000
-1
-1
The maximum number is ?
byte
The minimum number is ?
byte
What if we add the maximum number by 1 ???
What if we subtract the minimum number by 1 ???
TRU-COMP1380
Number Systems
+1
+1
+1
overflow
y = 125; y += 4; ??
x = -126; x -= 5; ??
27

16-bit representation with 2’s complement
...
...
...
3
2
1
0
-1
-2
-3
...
...
...


01111111 11111111
01111111 11111110
...
00000000 00000011
00000000 00000010
00000000 00000001
00000000 00000000
11111111 11111111
11111111 11111110
11111111 11111101
...
10000000 00000001
10000000 00000000
+1
+1
overflow
+1
short
y++;
short
x--;
overflow
y = 32767;
???
x = -32767;
???
-1
-1
-1
The maximum number is ? What if we add the maximum number by 1 ???
The minimum number is ? What if we subtract the minimum number by 1 ???
TRU-COMP1380
Number Systems
28


Note that computers use the 8-bit representation, the 16-bit
representation, the 32-bit representation and the 64-bit representation
with 2’complement for negative integers.
In programming lanaguages





byte,
short,
int,
long,
unsigned byte
unsigned short
unsigned int
unsigned long
8-bit
16-bit
32-bit
64-bit
When we use the 32-bit representation with 2’s complement,




The maximum number is ?
What if we add the maximum number by 1 ???
The minimum number is ?
What if we subtract the minimum number by 1 ???
TRU-COMP1380
Number Systems
29


How to convert a negative binary number to decimal?
An example of 8-bit representation,

10011001 = ???
TRU-COMP1380
Number Systems
30
Multiplication of Binary Numbers

How to multiply two decimal numbers?

E.g.,




1001101 × 1 = ???
1001101 × 10 = ???
1001101 × 100 = ???
1001101 × 101 = 1001101 × 10 × 10 + 1001101 × 0 + 1001101 × 1

What if we shift 1001101 left by one bit?
1001 -> 10010

What if we shift 1001101 left by two bits?
1001 -> 100100

Multiplication by a power of 2.
TRU-COMP1380
Number Systems
31
Division of Binary Numbers



Binary division?
1111
101
1001101
-101
1001
-101
1000
-101
111
-101
10
<- quotient
<- remainder
Try 1101011 / 110
Dividing negative binary numbers: division without sign, and then put
the sign.
TRU-COMP1380
Number Systems
32

Binary division by a power of 2?
1001101 / 10 = 100110
1001101 / 100 = 10011
1001101 / 1000 = 1001

What if we shift 1001101 right by 1 bit?
What if we shift 1001101 right by 2 bits?
What if we shift 1001101 right by 3 bits?

1001101 / 101 ???


TRU-COMP1380
Complicated implementation required
Number Systems
33
Fractions: Fixed-Point

How can we represent fractions?


Use “binary point” to separate positive from negative powers of two -like “decimal point.”
2’s complement addition and subtraction still work. (Assuming binary
points are aligned)
2-1 = 0.5
2-2 = 0.25
2-3 = 0.125
00101000.101 (40.625)
+ 11111110.110 (-1.25) (2’s complement)
00100111.011 (39.375)
No new operations -- same as integer arithmetic.
TRU-COMP1380
Number Systems
34

How to convert decimal fractions to binary?

0.62510 = ???2





0.625 * 2 = 1.25 -> 1
0.25 * 2 = 0.5 -> 0
0.5 * 2 = 1.0 -> 1
Therefore 0.101
(0.625 = x 2-1 + y 2-2 + z 2-3 + ...)
(1.25 = x + y 2-1 + z 2-2 + ... => x = 1)
(0.25 = y 2-1 + z 2-2 + ... )
0.710 = ???2









TRU-COMP1380
0.7 * 2 = 1.4 -> 1
0.4 * 2 = 0.8 -> 0
0.8 * 2 = 1.6 -> 1
0.6 * 2 = 1.2 -> 1
0.2 * 2 = 0.4 -> 0
0.4 * 2 = 0.8 -> 0
0.8 * 2 = 1.6 -> 1
...
Therefore 0.1011001...
How to deal with big numbers
and small numbers?
Number Systems
35
Very Large and Very Small: Floating-Point





Large values: 6.023 × 1023 -- requires 79 bits
Small values: 6.626 × 10-34 -- requires > 110 bits
How to handle those big/small numbers?
Use equivalent of “scientific notation”: F × 2E
Need to represent F (fraction), E (exponent), and sign.




6.023 × 1023 = 0.6023 × 1024
6.626 × 10-34 = 0.6626 × 10-33
00101000.101 (40.62510) = 0.101000101 × 26. Store 6 in the exponent and
101000101 in mantissa. (Try the multiplication)
IEEE 754 Floating-Point Standard (32-bits):
TRU-COMP1380
1b
8 bits
23 bits
S
Exponent
Fraction (mantissa)
Number Systems
36