Transcript Binary numbers

Binary numbers
Primary memory
• Memory = where programs and data are
stored
– Unit = bit
• “BIT” is a contraction for what two words?
• Either a 1 or a 0 (because computers are made
primarily of transistors which act as switches).
– Smallest addressable (i.e., can be read from or
written to memory) unit is the byte.
• byte = 8 bits (an 8-bit number)
Binary numbers
• How do computers represent numbers and do
arithmetic?
• How do we? What digits do we use? Why?
– What is 903?
• 9 is the MSD above; 3 is the LSD.
Binary numbers
• Can we represent numbers is other bases
(radix)?
– What is 11012 in base 10?
– What is 110110 in base 10?
– What is 11013 in base 10?
– Note that they are different!
Potential programming
asssignment
Write a program that reads in a string (not an
int) representing a binary number and
outputs the corresponding base 10 number.
Do not use any methods from Java’s Integer
class!
Potential programming
asssignment
Write a program that reads in a string (not an
int) (representing a # in base b), reads in the
base b (an int), and outputs the
corresponding base 10 number.
(What Java String method can be used to obtain
an individual char at a particular position in a
string?)
Do not use any methods from Java’s Integer
class!
Binary numbers
• What are the range of digits for base 10
numbers?
– For binary?
– For base 5?
– For some arbitrary base k?
– Is 11022 a valid base 2 number?
– Is 12644 a valid base 4 number?
Numbers in mathematics
• I = the integers
– Finite or infinite?
• R = the reals
– Contains rational numbers like 2/7 and irrational
numbers like 
– Finite or infinite?
• C = the complex numbers
– Finite or infinite?
Numbers in computers
• All represented by a finite sequence of bits
(1’s and 0’s).
• I = the integers
– Finite/bounded.
– char (8 bits), short (16 bits), int (32 bits), long long
(64 bits)
• R = the reals
– Finite/bounded. (So what about ?)
– float (32 bits), double (64 bits), long double (128
bits)
Numbers in computers
• R = the reals
– Finite/bounded. (So what about ?)
– Representation is called floating point.
– float (32 bits), double (64 bits), long double (128
bits)
– Can also be represented by fixed point and BCD
(binary coded decimal).
Common ranges of values (Java)
• int
-2 billion
• double 4.9x10-324
• float
1.4x10-45
(closest to 0)
(closest to 0)
to
+2 billion
to
1.8x10+308
to
3.4x10+38
Converting from base 10 to base 2
• Convert 6110 to base 2.
• Method 1: Subtract largest power of 2 repeatedly.
– Also works for both ints and floats.
– First, make a table of powers of 2.
•
•
•
•
•
•
•
•
•
28 = 256
27 = 128
26 = 64
25 = 32
24 = 16
23 = 8
22 = 4
21 = 2
20 = 1
Converting from base 10 to base 2
• Convert 6110 to base 2.
• Method 1: Subtract largest
power of 2 repeatedly.
1. Make a table of powers of 2.
•
•
•
•
•
•
•
•
•
28 = 256
27 = 128
26 = 64
25 = 32
24 = 16
23 = 8
22 = 4
21 = 2
20 = 1
2. Repeatedly subtract
(largest power of 2) 61
 32
29
 16
13
8
5
4
1
1
0
1  25
msb
1  24
1  23
1  22
0  21
1  20
lsb
Reading forward, the result
is 1111012.
Use this method to convert from
base 10 to base 3.
• Method 1: Subtract largest powers of 3
repeatedly.
Step 1: Create table of powers of 3.
•
•
•
•
•
34 = 81
33 = 27
32 = 9
31 = 3
30 = 1
Step 2: Repeatedly subtract (largest) multiples of
largest power of 3. (Why? Recall digit range for a
particular base.)
Use this method to convert from
base 10 to base 3.
• Method 1: Subtract
largest powers of 3
repeatedly.
Step 1: Create table of
powers of 3.
•
•
•
•
•
34 = 81
33 = 27
32 = 9
31 = 3
30 = 1
Step 2: Repeatedly subtract
(largest) multiples of
largest power of 3.
• Convert 6110 to base 3.
61
 54 2  33 msd
7 0  32
 6 2  31
1
 1 1  30 lsd
0
Reading forward, the
result is 20213.
Potential programming assignment
Write a program that takes as input a base 10
number (an int) and outputs the
corresponding base 2 number.
Do I need to remind you again? Do not use any
methods from Java’s Integer class!
Converting base 10 floating point numbers to
base 2 using Method 1 (repeated subtraction)
Step 1: Create table of powers of 2.
24 = 16
23 = 8
22 = 4
21 = 2
20 = 1
2-1 = 0.5
2-2 = 0.25
2-3 = 0.125
2-4 = 0.0625
2-5 = 0.03125
2-6 = 0.015625
Step 2: Subtract largest power of 2
repeatedly.
Converting base 10 floating point numbers to
base 2 using Method 1 (repeated subtraction)
Step 1: Create table of powers of 2.
24 = 16
23 = 8
22 = 4
21 = 2
20 = 1
2-1 = 0.5
2-2 = 0.25
2-3 = 0.125
2-4 = 0.0625
2-5 = 0.03125
2-6 = 0.015625
Step 2: Subtract largest power of 2
repeatedly.
Convert 11.07812510 to base 2.
11.078125
8
1  23
3.078125 0  22
2
1  21
1.078125
1
1  20
0.078125 0  2 1
0  2 2
 0.0625
0  2 3
1  2 4
0.015625 0  2 5
 0.015625 1  2 6
0
Reading forward, the result is
1011.0001012.
Conversion methods
Method 1. Using a table, repeatedly subtract
largest multiple.
- directly works for both ints and floats
- requires a table
Method 2: Repeated (integer) division (with
remainder) by desired base.
- works for ints but needs to be “modified” to
work for floats
- doesn’t require a table
Method 2: Repeated (integer) division
(with remainder) by desired base.
Convert 6110 to base 2.
61/ 2  30 61%2  1
30 / 2  15 30%2  0
15 / 2  7
7/2  3
15%2  1
7% 2  1
3/ 2  1
1/ 2  0
3% 2  1
1% 2  1
Reading backwards, the result is 1111012.
lsb
msb
Method 2: Repeated (integer) division
(with remainder) by desired base.
Convert 6110 to base 3.
61/ 3  20 61%3  1 lsd
20 / 3  6 20%3  2
6/3  2
2/3 0
6% 3  0
2%3  2 msd
Reading backwards, the result is 20213.
Method 2 for fp numbers
• Convert 61.687510 to base 2.
– We just saw how to convert 6110 to base 2 (by
repeated division with desired base).
– So all we need to do is convert 0.687510 to base 2.
– This can (analogously) be accomplished by
repeated multiplication by the desired base.
Method 2
• Convert 0.687510 to base 2 by repeated
multiplication by desired base.
0.6875 2  1.375
0.375 2  0.75
• Then read integer part forwards. 0.75  2  1.5
0.5  2  1.0
0.0  2  0.0
0.0  2  0.0

0.687510  0.10112
Method 2
• Convert 0.110 to base 2 by 0.1  2  0.2
repeated multiplication by
0 .2  2  0 .4
desired base.
0 .4  2  0 .8
• Then read integer part
forwards.
Do you see the
repetition/loop?
0 .8  2  1.6
0.6  2  1.2
0 .2  2  0 .4
0.110  0.000110011
...2
Method 2
• Convert 0.110 to base 2 by 0.1  2  0.2
repeated multiplication by
0 .2  2  0 .4
desired base.
same
0 .4  2  0 .8
• Then read integer part
forwards.
Do you see the
repetition/loop?
0 .8  2  1.6
0.6  2  1.2
0 .2  2  0 .4
same
0.110  0.000110011
...2
Converting between arbitrary
bases
• In general, to convert from base u to base v,
we typically:
– Convert from base u to base 10.
– Then convert from base 10 to base v.
• When converting from base 2 to two other
important bases, we can skip the intermediate
conversion through base 10 and convert
directly from base 2 to these two other bases
(and vice versa).
Other important bases related to
base 2: base 8
• Octal, base 8
– Digits: 0..7
base 8
0
1
2
3
4
5
6
7
• Problems:
base 2
000
001
010
011
100
101
110
111
– Convert 1008 to base 10.
– Convert 1008 to base 2.
– Convert 11012 to base 10.
– Convert 11012 to base 8.
– Convert 7028 to base 10.
– Convert 7028 to base 2.
– Convert 8028 to base 2.
Other important bases related to
base 2: base 16
•
Hex (hexadecimal), base 16
– Digits: 16 of them (more than base 10) so we’ll will need 6 extra symbols: {0..9,a..f}
base 16
0
1
2
3
4
5
6
7
8
9
a
b
c
d
e
f
base 10
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
base 2
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
base 8
00
01
02
03
04
05
06
07
10
11
12
13
14
15
16
17
Problems:
• Convert 7258 to base 2 to base 16 to base 10.
Problems:
• Convert 7258 to base 2 to base 16 to base 10.
– 111 010 1012
– 1 1101 01012 = 1d516
– 1x162 + 13x161 + 5x160 = 46910
Convert 153.51310 to base 8.
Approach: convert 153 and 0.513
separately.
153/ 8  19 1
19 / 8  2
3
2/8  0
2
0.513 8  4.104
0.104 8  0.832
remainder
So the result is
231.40651… base 8.
0.832 8  6.656
0.656 8  5.248
0.248 8  1.984

Problem: Convert 3115 to X10 to Y2.
• 3x52+1x51x1x50 = 75+5+1 = 8110.
81/ 2  40
40 / 2  20
20 / 2  10
10 / 2  5
5/ 2  2
2/2 1
1/ 2  0
1 lsb
0
0
0
1
0
1 msb
10100012
64  16  1  81