Transcript Number bases, addition and subtraction

Number Bases
Informatics INFO I101
February 9, 2004
John C. Paolillo, Instructor
Items for Today
• Last week
– Digital logic, Boolean algebra, and circuits
– Logic gates and truth tables
• This Week
– Numbers and bases
– Working with binary
Number Base Systems
The Format of a Base System
…
#
#
#
#
#
#
#
#
#
# …
… b4 b3 b2 b1 b0 b-1 b-2 b-3 b-4 b-5 …
The number represented is the sum of all the
products of the digit values and their respective
place values
Common Bases
•
•
•
•
Decimal (Base 10)
Binary (Base 2)
Octal (Base 8)
Hexadecimal (Base 16)
Conversion to Base 10
• Identify each of the places in the new number base. These
will correspond to the powers of the base, for example,
with base 2, they are 1, 2, 4, 8, 16, 32, etc.
• Multiply the value for each place by the value of the digit
appearing there;
• Add the results up, and you have the result in decimal
Note that if you divide and add correctly, you can reverse
this procedure to convert decimal into another base. It’s
harder, because you’re not used to using the appropriate
addition and multiplication tables.
Try out these examples
• What is 10011 Base 2 in decimal?
116+ 08 + 04 + 12 + 11 = 19
• What is 121 Base 8 in decimal?
164 + 28 + 11 = 81
• What is 247 Base 10 in Binary?
Here it helps to have a different procedure…
Converting to Binary
1
2
4
8
16
32
0
1
1
1
1
0
1
1
1
64
247
247
119
55
23
7
7
3
1
128
256
128
64
32
16
8
4
2
1
256
What we’re converting
28 27 26 25 24 23 22 21 20
0
1
1
1
1
0
1
1
1
Octal — base 8
• Sixteen digits:
0, 1, 2, 3, 4, 5, 6, 7
7 = 111two = 7eight
• Octal values are usually not specially
indicated
Unix example: chmod 666 myfile.html
Octal Digits
Decimal
0
1
2
3
4
5
6
7
Binary
000
001
010
011
100
101
110
111
Octal
0
1
2
3
4
5
6
7
Octal Tips
• each octal digit corresponds to three binary digits
(bits)
• convert binary to octal by parsing each group of
three bits into one octal digit
• convert octal to binary by translating each digit
into three bits
• Examples:
764eight
011011101two
=
=
111101100two
335eight
Hexadecimal — base 16
• Sixteen digits:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
15 = 1111two = Fsixteen
• Hexadecimal (“hex”) values are usually
indicated by a preceding base marker
HTML:
#FFFFFF
JavaScript, C: 0xF1AD
Hexadecimal Digits
Decimal
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Binary
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Hex
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
Hexadecimal Tips
• each hex digit corresponds to four binary
digits (bits)
• convert binary to hex by parsing each group
of four bits into one hex digit
• convert hex to binary by translating each
digit into four bits
• Two hex digits make up one byte, a very
common unit of memory
IP Numbers
IP = “Internet Protocol”
IP Number
129.79.142.114
Host Name
dhcp-Memorial–142-114.memorial.indiana.edu
A Domain Name Server (DNS) has a database that
matches IP and host name
The IP Number
• Four Fields
• 0-255 in each field
• This is really base
256, but we use
decimal numbers in
each digit
129.79.142.114
Net
Subnet
Node
Binary Addition
Adding in Binary
• Zero plus any other values leaves that value
Identity value for addition
No carry is generated
• One plus one leaves zero and causes a carry
(one) to the next digit
Each successive digit must accept the carry from
the previous
Try these calculations
01001101 Base 2
+ 00011011 Base 2
01111111 Base 2
+ 00000001 Base 2
102 Base 8
+ 121 Base 8
01001101 Base 2
 00000100 Base 2
0000101 Base 2
 0000101 Base 2
01111111 Base 2
 00011011 Base 2
Addition: Truth Tables
CI
0
0
0
0
1
1
1
1
A
0
1
0
1
0
1
0
1
B
0
0
1
1
0
0
1
1
S
0
1
1
0
1
0
0
1
CO
0
0
0
1
0
1
1
1
Addition: Half Adder
+
00
01 XOR 0
1
00
00
01
0
0
1
01
01
10
1
1
0

0
1
0
0
0
1
0
1
B
A
The half adder sends a carry, but can’t accept one
So we need another for the carry bit
S
C
Addition in Binary
• Two half-adders gives us a full adder
– two inputs plus carry
• Adders are cascaded to permit adding binary
numbers
– Eight adders allows adding (0...256) + (0...256) in
binary numbers
– Overflow can happen (200 + 100)
• Binary adders are used to do other computations
as well...
Subtraction
Complement Representations
Subtraction
–
00
01
00
00
01
01 –01 00
• Subtraction is
asymmetrical
• That makes it harder
• We have to borrow
sometimes
827 Minuend
–223 Subtrahend
=604 Difference/remainder
When Subtraction is Easy
456
–123
333
999
–123
876
• Subtraction is easy if you don’t
have to borrow
– i.e. if all the digits of the minuend
are greater than (or equal to) all
those of the subtrahend
• This will always be true if the
minuend is all 9’s: 999, or 999999,
or 9999999999 etc.
Using Easy Subtraction
• Subtract the subtrahend from 999 (or
whatever we need) (easy)
• Add the result to the minuend (ordinary
addition)
• Add 1 (easy)
• Subtract 1000 (drop highest digit)
Difference = Minuend + 999 – Subtrahend + 1
– 1000
This works for binary as well as decimal
Easy Subtraction in Binary
• Subtract the subtrahend from 111 (or
whatever we need) (easy)
• Add the result to the minuend (ordinary
addition)
• Add 1 (easy)
• Subtract 1000 (drop highest digit)
Difference = Minuend + 111 – Subtrahend + 1
– 1000
Binary Subtraction Example
10010101
–01101110
?????????
00100111
11111111
–01101110
10010001
+ 10010101
100100110
+1
100100111
–100000000
00100111
This is the same as
inverting each bit
Regular addition
Add one
Now drop the highest bit
(easy: it’s out of range)
Subtraction Procedure
Bitwise XOR
Each of theseCascaded
steps is aAdders
simple
operation we can perform using
Add carry bit
our logic circuits
Drop the highest
bit ( it overflows)
Invert each bit
Regular addition
Add one
Now drop the highest bit
(easy: it’s out of range)
Negative Numbers
Invert each bit
These steps make the negative
of a number in twos-complement
notation
Add one
• Twos complements can be added to other numbers normally
• Positive numbers cannot use the highest bit (the sign bit)
• This is the normal representation of negative numbers in binary
Negative Numbers in Binary
00000000
00000001
00000010
00000011
00000100
00000101
00000110
00000111
00001000
00001001
0
1
2
3
4
5
6
7
8
9
etc.
11111111
11111110
11111101
11111100
11111011
11111010
11111001
11111000
11110111
11110110
etc.
–1
–2
–3
–4
–5
–6
–7
–8
–9
–10
Representations
• The number representation you use
(encoding) affects the way you need to do
arithmetic (procedure)
• This is true of all codes: encoding
(representation) affects procedure
(algorithm)
• Good binary codes make use of properties
of binary numbers and digital logic
A problem
A computer program adds 20,000 and
20,000 and instead of 40,000, it reports –
25,566
• No errors in encoding, decoding or addition
• How? Because the result is a negative
number in twos-complement notation
(highest bit = sign bit)
How it works
• 20,000 base ten is 0100111000100000 binary
0100111000100000
0100111000100000
1001110001000000
• Highest bit is set, so number is negative in twos
complement notation: subtract one and invert to
display
1001110001000000 – 1 = 1001110000111111
0110001111000000 = 25,566
Bottom Line
• Representations themselves, as we use
them, have limits.
• Interpretation depends on context
• two procedures (encoding/decoding and
addition) may be in and of themselves
correct, but conflict in their application to
specific examples
MER has landed