Transcript a A 0 1 1 0

Binary Numbers
1
Outcome
• Familiar with the binary system
• Binary to Decimal and decimal to binary
• Arithmetic and logic operation in binary
system
• Logic gates
• Half Adder and Full Adder
• Hexadecimal system
Reading
• Goldsmiths Study guide:
– mathematics for computing
•
http://www.math.grin.edu/~rebelsky/Courses/152/97F/Readings/student-binary
•
http://en.wikipedia.org/wiki/Binary_numeral_system
•
http://www.cut-the-knot.org/do_you_know/BinaryHistory.shtml
•
http://www.binarymath.info/
The Decimal Number System (con’t)
• The decimal number system is also known as base 10. The
values of the positions are calculated by taking 10 to some
power.
• Why is the base 10 for decimal numbers?
o Because we use 10 digits, the digits 0 through 9.
4
The Binary Number System – base 2
• The decimal number system is a positional number system with a
base 10.
• Example: 5623
5000
5 x 103
•
600
6 x102
20
3
2 x 101
3 x 100
5623 = 5000 + 600 + 20 + 3 = 5 x 103 + 6 x102 + 2 x 101 + 3 x 100
5
The Binary Number System
• The binary number system is also known as base 2. The
values of the positions are calculated by taking 2 to some
power.
• Why is the base 2 for binary numbers?
o Because we use 2 digits, the digits 0 and 1.
6
The Decimal Number System - base 10
• The decimal number system is a positional number system with a
base 10.
• Example: 1011
1000
1 x 23
•
000
0x22
10
1
1 x 21
1x 20
10112 = 1000 + 000 + 10 + 1 = 1 x 23 + 0 x22 + 1 x 21 + 1 x 20 = 1110
7
Why Bits (Binary Digits)?
•
•
•
Computers are built using digital circuits
– Inputs and outputs can have only two values
– True (high voltage) or false (low voltage)
– Represented as 1 and 0
Can represent many kinds of information
– Boolean (true or false)
– Numbers (23, 79, …)
– Characters (‘a’, ‘z’, …) ASCII, UNICODE
– Pixels
– Sound
Can manipulate in many ways
– Read and write
– Logical operations
– Arithmetic
– …
8
Base 10 and Base 2
• Base 10
– Each digit represents a power of 10
– 5417310 = 5 x 104 + 4 x 103 + 1 x 102 + 7 x 101 + 3 x 100
• Base 2
– Each bit represents a power of 2
– 101012= 1 x 24 + 0 x 23 + 1 x 22 + 0 x 21 + 1 x 20 = 2110
9
Converting from Binary to Decimal
1 X 20 = 1
0 X 21 = 0
1 X 22 = 4
1 X 23 = 8
0 X 24 = 0
0 X 25 = 0
1 X 26 = 64
7710
1 0 0 1 1 0 1
26 25 24 23 22 21 20
20 = 1
21 = 2
22 = 4
23 = 8
24 = 16
25 = 32
26 = 64
10
Converting from Binary to Decimal (con’t)
Practice conversions:
Binary
110010
100111
1010101
11
Decimal
Converting From Decimal to Binary (con’t)
•
•
•
•
Make a list of the binary place values up to the number being converted.
Perform successive divisions by 2, placing the remainder of 0 or 1 in each of the
positions from right to left.
Continue until the quotient is zero.
Example:
4210
25 24 23 22 21 20
32 16 8 4 2 1
1 0 1 0 1 0
42/2 = 21
21/2 = 10
10/2 = 5
5/2 = 2
2/2 = 1
1/2 = 0
and
and
and
and
and
and
4210 = 1010102
R=0
R=1
R=0
R=1
R=0
R=1
12
Example 1710
We repeatedly divide the decimal number by 2 and keep remainders
–
–
–
–
–
17/2 = 8
8/2 = 4
4/2 = 2
2/2 = 1
1/2 = 0
and
and
and
and
and
R=1
R=0
R=0
R=0
R=1
The binary number representing 17 is 10001
Converting From Decimal to Binary (con’t)
Practice conversions:
Decimal
59
82
175
14
Binary
Fractional Numbers
Decimal
456.7810 = 4 x 102 + 5 x 101 + 6 x 100 + 7 x 10-1+8 x 10-2
Binary
1011.112 = 1 x 23 + 0 x 22 + 1 x 21 + 1 x 20 + 1 x 2-1 + 1 x 2-2
= 8 + 0 + 2 + 1 + 1/2 + ¼
= 11 + 0.5 + 0.25 = 11.7510
15
Binary Fractional to decimal nNumbers
(cont)
Example1
1011.112 = 1 x 23 + 0 x 22 + 1 x 21 + 1 x 20 + 1 x 2-1 + 1 x 2-2
= 8 + 0 + 2 + 1 + 1/2 + ¼
= 11 + 0.5 + 0.25 = 11.7510
•
•
Example 2:
111.112 = 1 x 22 + 1 x 21 + 1 x 20 + 1 x 2-1 + 1 x 2-2
=4 +
2 + 1 + 1/2 + ¼ = 7.7510
Example3: 11.0112 = 1 x 21 + 1 x 20 + 0x 2-1 + 1 x 2-2 + 1 x 2-3
= 2
+1
+0
+ ¼ +1/8 = 3.37510
16
Fractional numbers
Examples:
7.7510 = (?)2
1. Conversion of the integer part: same as before – repeated division by 2
7 / 2 = 3 (Q), 1 (R)  3 / 2 = 1 (Q), 1 (R)  1 / 2 = 0 (Q), 1 (R)
710 = 1112
2. Conversion of the fractional part: perform a repeated multiplication by 2 and
extract the integer part of the result
0.75 x 2 =1.50  extract 1
0.5 x 2 = 1.0  extract 1
0.7510 = 0.112
0.0
 stop
write in the same order

Combine the results from integer and fractional part, 7.7510 = 111.112
How about choose some of
4
2
Examples: try 5.625
1
1/2
1/4
=0.5
=0.25
1/8
=0.125
17
Fractional Numbers (cont.)
Exercise 3: Convert (0.8125)10 to its binary
form
Solution:
0.8125 x 2 = 1.625
 extract 1
0.625 x 2 = 1.25
 extract 1
0.25 x 2 = 0.5
 extract 0
0.5 x 2 = 1.0
 extract 1
0.0
 stop
 (0.8125)10 = (0.1101)2
18
Representing fraction with error
Example: Convert (0.6)10 to its binary form
0.6 x 2 = 1.2
 extract 1
0.2 x 2 = 0.4
 extract 0
0.4 x 2 = 0.8
 extract 0
0.8 x 2 = 1.6
 extract 1
0.6 x 2 =

(0.6)10 = (0.1001 1001 1001 …)2
19
Fractional Numbers (cont.)
• Errors
– One source of error in the computations is due to back and forth
conversions between decimal and binary formats
Example: (0.6)10 + (0.6)10 = 1.210
Since (0.6)10 = (0.1001 1001 1001 …)2
Lets assume a 8-bit representation: (0.6)10 = (0 .1001 1001)2 , therefore
0.6
0.10011001
+ 0.6
 +
0.10011001
1.00110010
Lets reconvert to decimal system:
(1.00110010)b= 1 x 20 + 0 x 2-1 + 0 x 2-2 + 1 x 2-3 + 1 x 2-4 + 0 x 2-5 + 0 x 2-6 + 1 x 2-7 + 0 x 2-8
= 1 + 1/8 + 1/16 + 1/128 = 1.1953125
 Error = 1.2 – 1.1953125
= 0.0046875
20
Bits, Bytes, and Words
•
•
•
•
•
•
A bit is a single binary digit (a 1 or 0).
A byte is 8 bits
A word is 32 bits or 4 bytes
Long word = 8 bytes = 64 bits
Quad word = 16 bytes = 128 bits
Programming languages use these standard number of
bits when organizing data storage and access.
21
Adding Two Integers: Base 10
• From right to left, we add each pair of digits
• We write the sum, and add the carry to the next column
0
1
1
+
0
0
1
2
Sum
1
0
0
1
Carry
0
1
1
1
9
8
+
2
6
4
Sum
4
6
Carry
0
1
22
Example
10011110
1101111
+
+
111
-------------------= 101 0 0 101
1101
------------------= 1111100
Binary subtraction
Binary subtraction (Cont)
Binary subtraction (Cont)
Exercise
• 10010101 - 11011 =?
• 10000001 - 111 = ?
Binary Multiplication
1 0 0 0 two = 8ten
1 0 0 1 two = 9ten
____________
multiplicand
multiplier
1000
0000
0000
1000
____________
1 0 0 1 0 0 0two = 72ten
Spring 2007, Jan. 17
partial products
ELEC 2200 (Agrawal)
28
Binary Division
13
11/147
11
37
33
4
Spring 2007, Jan. 17
Quotient
Divisor / Dividend
Partial remainder
Remainder
00001101
1011/10010011
1011
001110
1011
001111
1011
100
ELEC 2200 (Agrawal)
29
Bitwise Operators: Shift Left/Right
• Shift left (<<): Multiply by powers of 2
– Shift some # of bits to the left, filling the blanks with 0
53 0 0 1 1 0 1 0 0
53<<2
1 1 0 1 0 0 0 0
• Shift right (>>): Divide by powers of 2
– Shift some # of bits to the right
• For unsigned integer, fill in blanks with 0
• What about signed integers? Varies across machines…
– Can vary from one machine to another!
53 0 0 1 1 0 1 0 0
53>>2
0 0 0 0 1 1 0 1
30
Boolean Algebra to Logic Gates
• Logic circuits are built from components called
logic gates.
• The logic gates correspond to Boolean operations
+, *, ’.
OR
+
AND
*
NOT
’
• Binary operations have two inputs, unary has one
AND
Logic Gate:
A
A*B
B
A
B
Series Circuit:
A*B
Truth Table:
A
0
0
B
0
1
A*B
0
0
1
1
0
1
0
1
OR
Logic Gate:
A
A+B
B
A
Parallel Circuit:
B
A+B
Truth Table:
A
0
0
B
0
1
A+B
0
1
1
1
0
1
1
1
NOT
Logic Gate:
A
(also called an inverter)
A’ or A
Truth Table:
a
0
1
A
1
0
n-input Gates
• Because + and * are binary operations, they can be
cascaded together to OR or AND multiple inputs.
A
B
A
B
C
A+B+C
C
A+B+C
A
B
A
B
C
ABC
ABC
•
NAND
and
NOR
Gates
NAND and NOR gates can greatly simplify circuit diagrams. As we
will see, can you use these gates wherever you could use AND, OR,
and NOT.
NAND
NOR
A
B
AB
0
0
1
0
1
1
1
0
1
1
1
0
A
B
AB
0
0
1
0
1
0
1
0
0
1
1
0
XOR and XNOR Gates
• XOR is used to choose between two mutually exclusive
inputs. Unlike OR, XOR is true only when one input or the
other is true, not both.
XOR
XNOR
A
B
AB
0
0
0
0
1
1
1
0
1
1
1
0
A
B
A B
0
0
1
0
1
0
1
0
0
1
1
1
Binary Sums and Carries
a
0
0
1
1
b
0
1
0
1
Sum
0
1
1
0
a
0
0
1
1
XOR
b
0
1
0
1
Carry
0
0
0
1
AND
0100 0101
+ 0110 0111
69
103
1010 1100
172
38
Design Hardware Bit by Bit
• Adding two bits:
a
0
0
1
1
b
0
1
0
1
half_sum
0
1
1
0
carry_out
0
a
0
b
0
1
• Half-adder circuit
Spring 2007, Jan. 17
ELEC 2200 (Agrawal)
XOR
half_sum
AND
carry_out
39
Half Adder (1-bit)
A
B
Half
Adder
S
C
A
B
S(um)
C(arry)
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
Half Adder (1-bit)
A
Sum
B
S  AB  A B  A  B
C  AB
Carry
A
B
S(um)
C(arry)
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
Full Adder
A
Carry In
(Cin)
B
Full
Adder
S
Cout
Cin
A
B
S(um)
Cout
0
0
0
0
0
0
0
1
1
0
0
1
0
1
0
0
1
1
0
1
1
0
0
1
0
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1
Full Adder
S  Cin  A  B
Cout  AB  Cin(A  B)
A
B
H.A.
H.A.
S
Cin
Cout
Full Adder
S  Cin  A  B
Cout  AB  Cin(A  B)
A
A
S
A
Half
Adder
B
Cin
B
S
S
Half
Adder
C
B
C
Cout
4-bit Ripple Adder using Full Adder
Carry
A3
B3
A2
B2
A1
B1
A0
B0
A
B
A
B
A
B
A
B
Full
Cin
Adder
Cout
Full
Cin
Adder
Full
Cin
Adder
Cout
Cout
Full
Cin
Adder
Cout
S
S
S
S
S3
S2
S1
S0
S
A
B
C
Half Adder
S
Cout
A
H.A.
H.A. B
Cin
Full Adder
Working with Large Numbers
0101000010100111 = ?
• Humans can’t work well with binary numbers; there are too
many digits to deal with.
• Memory addresses and other data can be quite large.
Therefore, we sometimes use the hexadecimal number
system.
46
The Hexadecimal Number System
• The hexadecimal number system is also known as base 16. The values of
the positions are calculated by taking 16 to some power.
• Why is the base 16 for hexadecimal numbers ?
– Because we use 16 symbols, the digits 0 and 1 and the letters A
through F.
47
The Hexadecimal Number System (con’t)
Binary Decimal Hexadecimal
0
1
10
11
100
101
110
111
1000
1001
0
1
2
3
4
5
6
7
8
9
48
0
1
2
3
4
5
6
7
8
9
Binary Decimal Hexadecimal
1010
1011
1100
1101
1110
1111
10
11
12
13
14
15
A
B
C
D
E
F
The Hexadecimal Number System (con’t)
• Example of a hexadecimal number and the
values of the positions:
3 C 8 B 0 5 1
166 165 164 163 162 161 160
49
Example of Equivalent Numbers
Binary: 1 0 1 0 0 0 0 1 0 1 0 0 1 1 12
Decimal: 2064710
Hexadecimal: 50A716
Notice how the number of digits gets
smaller as the base increases.
50
Summary
•
•
•
•
•
Convert binary to decimal
Decimal to binary
Binary operation
Logic gates
Use of logic gates to perform binary operations
– Half adder
– Full adder
• The need of Hexadecimal Hexadecimal
Next lecture (Data representation)
• Put this all together
– negative and positive integer representation
– unsigned notation
– Signed notation
– Excess notation
– Tow’s complement notation
• Floating point representation
– Single and double precision
• Character, colour and sound representation