Transcript Data Structures CSCI 262, Spring 2002 Lecture 2 Classes and

Ethics of Computing
MONT 113G, Spring 2012
Session 3
Binary and Hexadecimal Numbers
1
Counting in Base 10
In the decimal number system (base 10), we use 10 digits 0 - 9.
We count until we run out of digits, and then add a new place with
value 10.
0 1 2 3 4 5 6 7 8 9 10
place value = 1
place value = 10
We continue to count, adding 1 to the 10's place every 10th number.
When we run out of digits for the 10's place, we add a new place
with value 102 (or 100).
... 98 99 100
place value = 100
2
Counting in Binary
With binary numbers, we have only 2 digits to work with (0 and
1), so we add places more frequently.
Each new place has a value that is a power of two.
Decimal
0
1
2
3
4
5
6
7
8
Binary
0
1
10
11
100
101
110
111
1000
Note: Each 1 or 0 is called
a binary digit or bit.
3
Base 10 vs. Base 2
In base 10, each place represents a power of 10:
4173 = ?
4 x 103 + 1 x 102 + 7 x 10 + 3 x 100
In base 2, each place represents a power of 2:
10110 = ?
1 x 24 + 0 x 23 + 1 x 22 + 1 x 2 + 0 x 20 = 22
Practice:
Convert 110110 from binary to decimal.
4
Converting from Decimal to
Binary--Method 1
To convert from decimal to binary, we first find the largest power of 2 that is
less than or equal to our decimal number.
We divide by that number and put the result in the binary place associated
with that power of two.
We then repeat with the remainder from the previous division.
Example: Convert 25 (base 10) to binary.
The largest power of 2 that divides 25 is 16.
25/16 = 1
R=9
9/8 = 1
R=1
1/4 = 0
R=1
1/2 = 0
R=1
1/1 = 1
R=0
Binary number = 11001
5
Converting from Decimal to
Binary--Method 2
Method 2:
Divide repeatedly by 2.
Place remainders in order from right to left.
Example:
25/2 = 12
R=1
12/2 = 6
R=0
6/2 = 3
R=0
3/2 = 1
R=1
1/2 = 0
R=1
Result = 11001
Practice: What is 43 written in base 2?
6
Hexadecimal Numbers
Hexadecimal numbers use base 16.
To count in base 16, we use the letters A - F to stand for decimal equivalents
of 11 - 15.
Base 10
0
1
2
...
9
10
11
12
13
14
15
16
Base 16
0
1
2
...
9
A
B
C
D
E
F
10
Base 10
...
255
256
Base 16
...
FF
100
162 = 256
7
Converting from Binary to
Hexadecimal
Every 4 bits represents 1 hexadecimal digit.
To convert from binary to Hexadecimal, group the bits into sets of
four (from right to left) and find the corresponding hexadecimal digit
for each set of 4 bits.
1011 0011
B
3
1101 0110
?
?
8
Representing Integers
How many integers can you represent with n bits?
1 bit:
0
1
2 bits:
00
01
10
11
3 bits:
000
001
010
011
100
101
110
111
n bits: ?
9
Signed Magnitude
We want to represent both positive and negative integers. How?
Method 1 (Signed Magnitude): Use leftmost bit to indicate the
sign.
1 => negative number
0 => positive number
Example: Assume an 8 bit integer, represent +3 and -3
+3 = ?
+3 = 00000011
-3 = ?
-3 = 10000011
10
One's Complement
Method 2: One's Complement.
1st digit represents the sign (1 => negative)
If the number is negative, take the positive representation and
flip each bit (from 1 to 0 or from 0 to 1).
Example:
+3 = ?
+3 = 00000011
-3 = ?
-3 = 11111100
11
Two's Complement
Method 3: Two's complement
1st digit represents the sign (1 => negative)
If the number is negative, take the positive representation
and flip each bit (from 1 to 0 or from 0 to 1) and add 1.
Example:
+3 = ?
+3 = 00000011
-3 = ?
-3 = 11111101
12
Binary Addition
Addition: adding two positive numbers
Add 14 and 11:
14
+11
25
00001110
00001011
00011001
(Check result)
Subtraction: add a negative number to a positive number
Subtract 11 from 14.
14
- 11
3
00001110
- 00001011
00001110
+11110101
00000011
13
When the numbers are too big
What happens when we add 127 to 60, using 8 bit integers?
127
+60
187
01111111
00111100
10111011 = -69
What is the largest number we can represent with n bits?
1 bit for the sign.
Can represent 2n-1 -1 as the largest number.
With 8 bits, can represent 27 -1 = 127
14
Floating point representation
Floating point (real) numbers use 32 bits:
1 sign bit
7 bits for exponent
24 bit fraction
Recall scientific notation: 18,000 = 1.8 x 104
Example: 0 1000011 10101000 ... (rest zeros)
Sign is zero => positive
Exponent = + 3 (sign bit for exponent uses 1 for positive)
Fraction = .10101
23 x .10101 = 101.01 = 1 x 4 + 0 x 2 + 1 x 1 + 0 x .5 + 1 x .25
= 5.25
15