Transcript computer_math3

Computer Math
CPS120: Lecture 3
Binary and Computers
Binary computers have storage units called binary
digits or bits:
Low Voltage = 0
High Voltage = 1
all bits have 0 or 1
22
Binary and Computers
8 bits = 1 byte
The number of bytes in a word determines the
word length of the computer:
32-bit machines
64-bit machines etc.
23
Binary Representations
One bit can be either 0 or 1. Therefore,
one bit can represent only two things.
 To represent more than two things, we
need multiple bits. Two bits can
represent four things because there are
four combinations of 0 and 1 that can
be made from two bits: 00, 01, 10,11.

Binary Representations (Cont’d)

If we want to represent more than four
things, we need more than two bits.
Three bits can represent eight things
because there are eight combinations of
0 and 1 that can be made from three
bits.
Binary & Alphanumeric Codes

A binary code is a group of n bits that
assume up to 2n distinct combinations
of 1’s and 0’s with each combination
representing one element of the set
that is being coded- i.e. permutations
With two bits we can form a set of four
elements
 With three bits we can represent 8 elements
 With four bits we can represent 16 elements

Binary Representations (Cont’d)
Figure 3.4
Bit combinations
Binary Representations (Cont’d)

In general,  bits can represent 2
things because there are 2
combinations of 0 and 1 that can be
made from n bits. Note that every time
we increase the number of bits by 1, we
double the number of things we can
represent.
Memory Units






1
1
1
1
1
1
nibble
byte
word
long word
quad word
octa-word






4 consecutive bits
8 consecutive bits
2 consecutive bytes
4 consecutive bytes
8 consecutive bytes
16 consecutive bytes
Larger Units of Memory






1
1
1
1
1
1
Kilobyte
Megabyte
Gigabyte
Terabyte
Petabyte
Exabyte






1024 bytes
~106 bytes
~109 bytes
~1012 bytes
~1015 bytes
~1018 bytes
32 Mb = 32*103 Kb = 32 * 103 *1024 bytes = 32,768,000 bytes
Representing Data

The computer knows the type of data stored
in a particular location from the context in
which the data are being used;


i.e. individual bytes, a word, a longword, etc
01100011 01100101 01000100 01000000



Bytes: 99(10, 101 (10, 68 (10, 64(10
Two byte words: 24,445 (10 and 17,472 (10
Longword: 1,667,580,992 (10
Numbers
Natural Numbers
Zero and any number obtained by repeatedly adding
one to it.
Examples: 100, 0, 45645, 32
Negative Numbers
A value less than 0, with a – sign
Examples: -24, -1, -45645, -32
2
Numbers
(Cont’d)
Integers
A natural number, a negative number, zero
Examples: 249, 0, - 45645, - 32
Rational Numbers
An integer or the quotient of two integers
Examples: -249, -1, 0, ¼ , - ½
3
Natural Numbers
How many ones are there in 642?
600 + 40 + 2 ?
Or is it
384 + 32 + 2 ? -- Octal
Or maybe…
1536 + 64 + 2 ? -- Hexadecimal
4
Natural Numbers
642 is 600 + 40 + 2 in BASE 10
The base of a number determines the number
of digits and the value of digit positions
5
Positional Notation
Continuing with our example…
642 in base 10 positional notation is:
6 x 10² = 6 x 100 = 600
+ 4 x 10¹ = 4 x 10 = 40
+ 2 x 10º = 2 x 1 = 2
= 642 in base
10
This number is in
base 10
The power indicates
the position of
the number
6
Positional Notation
R is the base
of the number
As a formula:
dn * Rn-1 + dn-1 * Rn-2 + ... + d2 * R +
d1
n is the number of
digits in the number
642 is:
63 * 102 + 42 * 10 + 21
d is the digit in the
ith position
in the number
7
Positional Notation
What if 642 has the base of 13?
+ 6 x 13² = 6 x 169 = 1014
+ 4 x 13¹ = 4 x 13 = 52
+ 2 x 13º = 2 x 1 = 2
= 1068 in base 10
642 in base 13 is equivalent to
1068 in base 10
8
6
Binary
Decimal is base 10 and has 10
digits:
0,1,2,3,4,5,6,7,8,9
Binary is base 2 and has 2 digits:
0,1
For a number to exist in a given number system, the
number system must include those digits. For
example:
The number 284 only exists in base 9 and higher.
9
Codes
Given any positive integer base (RADIX)
N, there are N different individual symbols
that can be used to write numbers in the
system. The value of these symbols range
from 0 to N-1
 All systems we use in computing are
positional systems


495 = 400 + 90 +5
Number Systems
 We
use the DECIMAL (10 system
 Computers use BINARY (2 or some
shorthand for it like OCTAL (8 or
HEXADECIMAL (16
Power of 2 Number System
Binary
000
001
Octal
0
1
Decimal
0
1
010
011
100
101
2
3
4
5
2
3
4
5
110
111
6
7
6
7
100
10
8
1001
1010
11
12
9
10
16
Bases Higher than 10
How are digits in bases higher than 10
represented?
Base 16:
0,1,2,3,4,5,6,7,8,9,A,B,C,D,E, and F
10
Conversions
Decimal
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Binary
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
Octal
0
1
2
3
4
5
6
7
10
11
12
13
14
15
16
Hex
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
Decimal Equivalents

Assuming the bits are unsigned, the
decimal value represented by the bits of
a byte can be calculated as follows:
1.
Number the bits beginning on the right using
superscripts beginning with 0 and increasing as
you move left
•
2.
3.
4.
Note: 20, by definition is 1
Use each superscript as an exponent of a power
of 2
Multiply the value of each bit by its
corresponding power of 2
Add the products obtained
Converting Octal to Decimal
What is the decimal equivalent of the octal
number 642?
6 x 8² = 6 x 64 = 384
+ 4 x 8¹ = 4 x 8 = 32
+ 2 x 8º = 2 x 1 = 2
= 418 in base 10
11
Converting Hexadecimal to
Decimal
What is the decimal equivalent of the
hexadecimal number DEF?
D x 16² = 13 x 256 = 3328
+ E x 16¹ = 14 x 16 = 224
+ F x 16º = 15 x 1 = 15
= 3567 in base 10
Remember, base 16 is
0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
Converting Binary to Decimal
What is the decimal equivalent of the binary
number 1101110?
1 x 26
+ 1 x 25
+ 0 x 24
+ 1 x 23
+ 1 x 22
+ 1 x 21
+ 0 x 2º
=
=
=
=
=
=
=
1 x 64 = 64
1 x 32 = 32
0 x 16 = 0
1x8 =8
1x4 =4
1x2 =2
0x1 =0
= 112 in base 10
13
Horner’s Method

Another procedure to calculate the decimal
equivalent of a binary number


Note: This method works with any base
Horner’s Method:





Step
Step
Step
Step
Step
digit
1:
2:
3:
4:
5:
Start with the first digit on the left
Multiply it by the base
Add the next digit
Multiply the sum by the base
Continue the process until you add the last
Converting Binary to Octal
• Groups of Three (from right)
• Convert each group
10101011
10 101 011
2 5 3
10101011 is 253 in base 8
17
Binary to Hex

Step 1: Form four-bit groups beginning from
the rightmost bit of the binary number

If the last group (at the leftmost position) has less
than four bits, add extra zeros to the left of the
group to make it a four-bit group



0110011110101010100111 becomes
0001 1001 1110 1010 1010 0111
Step 2: Replace each four-bit group by its
hexadecimal equivalent

19EAA7(16
Converting Decimal to Other
Bases



Step 1: Divide the number by the base you
are converting to (r)
Step 2: Successively divide the quotients by
(r) until a zero quotient is obtained
Step 3: The decimal equivalent is obtained by
writing the remainders of the successive
division in the opposite order in which they
were obtained


Know as modulus arithmetic
Step 4: Verify the result by multiplying it out
Converting Decimal to
Hexadecimal
222
16 3567
32
36
32
47
32
15
13
16 222
16
62
48
14
0
16 13
0
13
D E F
21
Addition & Subtraction Terms

A+B



A is the augend
B is the addend
C–D


C is the minuend
D is the subtrahend
Addition Rules – All Bases
Addition
 Step 1: Add a column of numbers
 Step 2: Determine if there is a single
symbol for the result
 Step 3: If so, write it and go to the
next column. If not, write the
accompanying number and carry the
appropriate value to the next column
Addition of Binary Numbers

Rules for adding or subtracting very
similar to the ones in decimal system

0
0
1
1

Limited to only two digits
+
+
+
+
0
1
0
1
=
=
=
=
0
1
1
0 carry 1
Arithmetic in Binary
Remember: there are only 2 digits in binary:
0 and 1
Position is key, carry values are used:
1 11111
1010111
+1 0 0 1 0 1 1
10100010
Carry Values
14
Number Overflow

Overflow occurs when the value that we
compute cannot fit into the number of bits we
have allocated for the result. For example, if
each value is stored using eight bits, adding
127 to 3 overflow:
01111111
+ 00000011
10000010

Overflow is a classic example of the type of
problems we encounter by mapping an
infinite world onto a finite machine.
Subtraction Rules – All Bases


Step1: Start with the rightmost column, if the
column of the minuend is greater than that of
the subtrahend, do the subtraction, if not…
Step 2: Borrow one unit from the digit to the
left of the once being processed



The borrowed unit is equal to “borrowing” the
radix
Step 4: Decrease the column form which you
borrowed by one
Step 3: Subtract the subtrahend from the
minuend and go to the next column
Subtracting Binary Numbers
Remember borrowing? Apply that concept
here:
1 2
202
1010111
- 111011
0011100
15
Addition & Subtraction of Hex



Due to the propensity for errors in binary, it is
preferable to carry out arithmetic in
hexadecimal and convert back to binary
If we need to borrow in hex, we borrow 16
It is convenient to think “in decimal” and then
translate the results back to hex
Representing Real Numbers


Real numbers have a whole part and a
fractional part. For example 104.32,
0.999999, 357.0, and 3.14159 the digits
represent values according to their position,
and those position values are relative to the
base.
The positions to the right of the decimal point
are the tenths position (10-1 or one tenth),
the hundredths position (10-2 or one
hundredth), etc.
Representing Real Numbers
(Cont’d)
In binary, the same rules apply but the
base value is 2. Since we are not
working in base 10, the decimal point
is referred to as a radix point.
 The positions to the right of the radix
point in binary are the halves position
(2-1 or one half), the quarters position
(2-2 or one quarter), etc.

Representing Real Numbers
(Cont’d)

A real value in base 10 can be defined
by the following formula:

The representation is called floating
point because the number of digits is
fixed but the radix point floats.
Representing Real Numbers
(Cont’d)

Likewise, a binary floating –point value is
defined by the following formula:
sign * mantissa * 2exp
Representing Real Numbers
(Cont’d)


Scientific notation is a term with which you
may already be familiar, so we mention it
here. Scientific notation is a form of floatingpoint representation in which the decimal
point is kept to the right of the leftmost digit.
For example, 12001.32708 would be written
as 1.200132708E+4 in scientific notation.
Representing Text



To represent a text document in digital form, we simply
need to be able to represent every possible character that
may appear.
There are finite number of characters to represent. So the
general approach for representing characters is to list them
all and assign each a binary string.
A character set is simply a list of characters and the
codes used to represent each one. By agreeing to use a
particular character set, computer manufacturers have
made the processing of text data easier.
Alphanumeric Codes

American Standard Code for Information
Interchange (ASCII)





7-bit code
Since the unit of storage is a bit, all ASCII codes
are represented by 8 bits, with a zero in the most
significant digit
H e l
l o
W o r l d
48 65 6C 6C 6F 20 57 6F 72 6C 64
Extended Binary Coded Decimal Interchange
Code (EBCDIC)
The ASCII Character Set
ASCII stands for American Standard
Code for Information Interchange. The
ASCII character set originally used
seven bits to represent each character,
allowing for 128 unique characters.
 Later ASCII evolved so that all eight bits
were used which allows for 256
characters.

The ASCII Character Set
(Cont’d)
The ASCII Character Set

(Cont’d)
Note that the first 32 characters in the
ASCII character chart do not have a
simple character representation that
you could print to the screen.
The Unicode Character Set



The extended version of the ASCII character
set is not enough for international use.
The Unicode character set uses 16 bits per
character. Therefore, the Unicode character
set can represent 216, or over 65 thousand,
characters.
Unicode was designed to be a superset of
ASCII. That is, the first 256 characters in the
Unicode character set correspond exactly to
the extended ASCII character set.
The Unicode Character Set
(Cont’d)
A few characters in the Unicode character set
Representing Signed Numbers

Remember, all numeric data is represented
inside the computer as 1s and 0s


Arithmetic operations, particularly subtraction raise
the possibility that the result might be negative
Any numerical convention needs to
differentiate two basic elements of any given
number, its sign and its magnitude

Conventions




Sign-magnitude
Ten's complement
Two’s complement
One’s complement
Representing Negatives

It is necessary to choose one of the bits of
the “basic unit” as a sign bit




Usually the leftmost bit
By convention, 0 is positive and 1 is negative
Positive values have the same representation
in all conventions
However, in order to interpret the content of
any memory location correctly, it necessary to
know the convention being used used for
negative numbers
Comparing the Conventions
Bit Pattern
000
001
010
011
100
101
110
111
Unsigned
0
1
2
3
4
5
6
7
Sign1's
2's
Magnitude Complement Complement
0
0
0
1
1
1
2
2
2
3
3
3
-0
-3
-4
-1
-2
-3
-2
-1
-2
-3
-0
-1
Representing Negative Values

You have used the signed-magnitude
representation of numbers since
grade school. The sign represents the
ordering, and the digits represent the
magnitude of the number.
Representing Negative Values
(Cont’d)

There is a problem with the signmagnitude representation:


There are two representations of zero.
There is plus zero and minus zero. Two
representations of zero within a computer
can cause unnecessary complexity.
Sign-Magnitude
For a basic unit of N bits, the leftmost
bit is used exclusively to represent the
sign
 The remaining (N-1) bits are used for
the magnitude
 The range of number represented in
this convention is –2 N+1 to +2 N-1 -1

Sign-magnitude Operations

Addition of two numbers in sign-magnitude is
carried out using the usual conventions of
binary arithmetic



If both numbers are the same sign, we add their
magnitude and copy the same sign
If different signs, determine which number has the
larger magnitude and subtract the other from it.
The sign of the result is the sign of the operand
with the larger magnitude
If the result is outside the bounds of –2 n+1 to +2
n-1 –1, an overflow results
Other Ways of Representing
Negative Values
If we allow only a fixed number of values, we
can represent numbers as just integer values,
where half of them represent negative
numbers.
 For example, if the maximum number of
decimal digits we can represent is two, we can
let 1 through 49 be the positive numbers 1
through 49 and let 50 through 99 represent the
negative numbers -50 through -1.

Representing Negative Values
(Cont’d)

To perform addition within this scheme,
you just add the numbers together and
discard any carry.
Representing Negative Values
(Cont’d)

A-B=A+(-B). We can subtract one
number from another by adding the
negative of the second to the first.
Representing Negative Values
(Cont’d)

There is a formula that you can use to
compute the negative representation:

This representation of negative
numbers is called the ten’s
complement.
Representing Negative Values
(Cont’d)
Two’s Complement:
To make it easier to look at
long binary numbers, we
make the number line
vertical.
Representing Negative Values
(Cont’d)

Addition and subtraction are
accomplished the same way as in 10’s
complement arithmetic:
-127 10000001
+ 1 00000001
-126 10000010

Notice that with this representation,
the leftmost bit in a negative number
is always a 1.
Two’s Complement Convention


A positive number is represented using a
procedure similar to sign-magnitude
To express a negative number
1.
2.
3.
–
–
Express the absolute value of the number in binary
Change all the zeros to ones and all the ones to zeros
(called “complementing the bits”)
Add one to the number obtained in Step 2
The range of negative numbers is one
larger than the range of positive numbers
Given a negative number, to find its positive
counterpart, use steps 2 & 3 above
Two’s Complement Operations

Addition:

Treat the numbers as unsigned integers



The sign bit is treated as any other number
Ignore any carry on the leftmost position
Subtraction


Treat the numbers as unsigned integers
If a "borrow" is necessary in the leftmost place,
borrow as if there were another “invisible” one-bit
to the left of the minuend
Overflows in Two’s Complement



The range of values in two’s-complement is –
2 n+1 to +2 n-1 –1
Results outside this band are overflows
In all overflow conditions, the sign of the
result of the operation is different than that of
the operands


If the operands are positive, the result is negative
If the operands are negative, the result is positive
One’s Complement
Devised to make the addition of two
numbers with different signs the same as
two numbers with the same sign
 Positive numbers are represented in the
usual way
 For negatives



STEP 1: Start with the binary representation of
the absolute value
STEP 2: Complement all of its bits
One's Complement Operations


Treat the sign bit as any other bit
For addition, carry out of the leftmost bit is
added to the rightmost bit – end-around
carry