Transcript to - CodeDuniya.com

Problem Solving using computers
Data..
Representation & storage
Representation of Numeric data
The Binary System
1
What Types Of Numbers ?
Number A representation of the count of things
• Natural Numbers
– The Number 0;
– Any number obtained by repeatedly adding a count of 1 to the
previous, starting with 0;
– Think of them as ‘counting up’ from the 0;
• Negative Numbers
– A value less than 0;
– Represents a ‘count down’ from the 0;
• Integer
A Natural Number, a negative of a natural number, or 0.
An integer number system is a system for
‘counting things’ in a simple systematic way.
2
Problem statement
•
•
•
•
Develop a scheme for representation of numbers using bits
(lets focus on positive integer numbers).
Can we represent numbers as we did for text data ? (i.e.
represent each digit appearing in the number by its
corresponding 8-bit ASCII code (Click here ).
For example,The representation of 37 will be:
00110011 00110111
3
7
Disadvantage? Non economical. if we are restricted to use bit
patterns of length 16 for each number , how many possible
numbers can we represent ?
Shockingly … only the numbers from 00 to 99 , why?
Representing numbers by the ASCII codes of their digits is
grossly inefficient, any alternatives?
3
Lets imitate what we know;
The Decimal System
• How is a positive integer represented in the decimal system?
• For example why is 375 equal to three hundred and seventy five?
375 = 3 *100 + 7 * 10 + 5*1
= 3*102 + 7 * 101 + 5*100
• Another look at 375
Position weights
Number digits
102 101 100
3
7
5
5*100 =
5+
7*101 = 70
+
3*102 = 300
375
4
• Position weights are powers of 10; The weight of the
right most (least significant position) is 100.
7
0
Digits of the number
• The value contributed by a digit equals the product
of the digit times the weight of the position of the digit
in the number.
Position weights
• Each digit contributes to value the number represents.
3
• A number is a sequence of digits . Any digit must be in
the set {0,1,2,3,4,5,6,7,8,9} (that’s why its is called
base 10 system).
104 103 102 101 100
Lets imitate what we know;
Decimal System principles
• The weight of any position 10x, where x is the number
of positions to the right of this position.
5
Lets imitate what we know;
From Decimal to binary
•
What if all we had was bits ? Meaning that the only possible digits we can
write into a bit are {0,1}?
•
Lets apply all the principles of base 10 system to construct a “base 2
system”
Position weights
digits
24
23
22
21
1
0
1
20
1
6
Converting a number in base
2 to its base 10 equivalent
Example
• The number 100101 represented in base 2 system
(written (100101)2 ) =
1*20+
0*21+
1*22+
0*23+
0*24+
1*25
(37)10
7
Converting a number in base 10 to its
base 2 equivalent
• (125)10 = (? )2 (i.e. the number 125 in base 10 is equal to what in
base 2?)
• There is a standard algorithm we can apply to answer this question:
– (1) Start with your number, call it n, in base 10;
– (2) Divide n by 2 and record the remainder;
– (3) If the quotient = 0 stop,
else
Assign the quotient value to n, and go to step
2;
• When you stop the remainders recorded will be the digits of the
number in base 2 in the positions from rightmost to leftmost;
• Lets apply this algorithm to an example.
8
Converting a number in base 10 to its
base 2 equivalent
• (125)10 = (? )2
9
Base 2 System
Versus
ASCII encoding of digits
• Assume can only use 16 bits to represent each positive integer, how
many different numbers can we represent:
– Using the ASCII encoding of digits?
– Using base 2 system?
• Answer
– Using ASCII encoding (only the number from 0 – 99 can be
represented; a total of 100 distinct numbers)
– Using Base 2 system
• We have 216 distinct bit patterns; each can be used to
represent a distinct number; a total of 65536 distinct numbers
• The numbers will be in the range: zero
(0000000000000000)2 to 65535 (1111111111111111)2
10
Base 2 System Arithmetic
Addition
• We represent Numbers because we need to do Arithmetic
operations on them;
• Can we do arithmetic on numbers represented in base 2 ?
Yes
• Consider Addition; When we first did it in elementary
school we had to learn and memorize addition facts
• For the binary system the following are the addition facts
• 0+0=0
• 0+1=1
• 1+0=1
• 1 + 1 = 10 (i.e. 0 and carry 1)
11