Transcript Number Systems: Positive Integers

Department of Computer and Information Science,
School of Science, IUPUI
CSCI N305
Information Representation:
Positive Integers
Dale Roberts
Information Representation
Computer use a binary systems
Why binary?
Electronic bi-stable environment
on/off, high/low voltage
Bit: each bit can be either 0 or 1
1
0
1
0
1
0
-3 mv
0 mv
Reliability
Digital v.s, Analog
With only 2 values, can be widely separated, therefore clearly
differentiated
“drift” causes less error
Example:
1 0 010101
10 000001
Dale Roberts
• Binary Representation in Computer System
– All information of diverse type is represented within
computers in the form of bit patterns.
• e.g., text, numerical data, sound, and images
– One important aspect of computer design is to decide
how information is converted ultimately to a bit pattern
– Writing software also frequently requires understanding
how information is represented along with accuracies
Dale Roberts
Number Systems
Decimal Number System
Base is 10 or ‘D’ or ‘Dec’
Ten symbols: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Each place is weighted by the power of 10
Example:
1234.2110 or 1234.21D
= 1 x 103 + 2 x 102 + 3 x 101 + 4 x 100 + 2 x 10 -1 + 1 x 10 -2
= 1000 + 200 + 30 + 4 + 0.2 + 0.01
$1,000
$100
$10
$1
10¢
1¢
Dale Roberts
Binary Number System
Binary Number System
Base is 2 or ‘b’ or ‘B’ or ‘Bin’
Two symbols: 0 and 1
Each place is weighted by the power of 2
Example:
10112 or 1011 B
= 1 x 23 + 0 x 22 + 1 x 21 + 1 x 20
= 8 + 0 + 2 +1
= 1110
11 in decimal number system is 1011 in binary number system
Dale Roberts
Conversion between Decimal and Binary
Conversion from decimal number system to binary
system
Question: represent 3410 in the binary number system
Answer: using the divide-by-2 technique repeatedly
34
17
div-by-2
8
div-by-2
0
4
div-by-2
1
2
div-by-2
0
1
div-by-2
0
div-by-2
0
1
Remainder
If we write the remainder from right to left :
3410  1 x 25 + 0 x 24 + 0 x 23 + 0 x 22+ 1x 21 + 0 x 20
 1000102
Dale Roberts
Practice Exercises
Blocks: 512 256 128 64 32 16 8 4 2 1
13D = (?) B
8
32 16 8 4 2 1
2
4
8
1
16
1
1101B
4
23D = (?) B
2
8
16
4
1
72D = (?) B
64
8
32
16
2
4
1
Dale Roberts
Conversion between Binary and Decimal
Conversion from binary number system to
decimal system
Example: check if 1000102 is 3410
using the :weights” appropriately
1000102  1 x 25 + 0 x 24 + 0 x 23 + 0 x 22+ 1 x 21 + 0 x 20
 32 +
0
+
0
+ 0
+ 2
+ 0
 3410
Dale Roberts
Practice Exercises
Ex: 0101B ( ? ) D
Bit 4
23 = 8
Bit 3
22 = 4
Bit 2
21 = 2
Bit 1
20 = 1
0
1
0
1
Ex: 1100B  ( ? ) D
4
+
1
= 5D
1 1 0 0
8 4 2 1 = 12D
Ex: 0101 1100B  ( ? ) D
0
1
0
1
1
1
0
0
128
64
32
16
8
4
2
1
= 92D
Dale Roberts
Binary Arithmetic on Integers
Addition
a
0
0
1
1
b
0
1
0
1
a+b
0
1
1
10
Carry bit
1 1
Example: find binary number of a + b
• If a = 13D , b = 5D
13D
+ 5D
18D
+
1
1 1 0 1b
0 1 0 1b
1 0 0 1 0b
1 1 1
• If a = 15D, b = 10D
15D
+ 10D
25D
1 1 1 1b
+ 1 0 1 0b
1 1 0 0 1b
Dale Roberts
Binary Arithmetic on Integers
Multiplication
a
0
0
1
1
b
0
1
0
1
axb
0
0
0
1
Example: if a = 100001b , b = 101b , find a x b
x
1 0 0 0 0 1b
1 0 1b
 33D
 5D
100001
0000000
10000100
1 0 1 0 0 1 0 1b  165D
Dale Roberts
Hexadecimal Number System
Hexadecimal Number System
Base = 16 or ‘H’ or ‘Hex’
16 symbols:
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A(=10), B(=11), C(=12), D(=13), E(=14), F(=15)}
Hexadecimal to Decimal
(an-1an-2…a1a0)16 = (an-1 x 16n-1 + an-2 x 16n-2 + …+ a1 x 161 + a0 x 160 )D
Example: (1C7)16 = (1 x 162 + 12 x 161 + 7 x 160 )10 = (256 + 192 + 7)10 = (455)10
Decimal to Hexadecimal
Repeated division by 16
Similar in principle to generating binary codes
Example: (829)10 = (? )16
Divide-by-16
829 / 16
51 / 16
3 / 16
Quotient
Remainder
51
3
0
13
3
3
Hexadecimal digit
Lower digit = D
Second digit =3
Third digit =3
Stop, since quotient = 0
Hence, (829)10 = (33D)16
Dale Roberts
Hexadecimal Conversions
Hexadecimal to Binary
Expand each hexadecimal digit to 4 binary bits.
Example:
(E29)16 = (1110 | 0010 | 1001)2
Binary to Hexadecimal
Combine every 4 bits into one hexadecimal digit
Example:
(0101 | 1111 | 1010 | 0110)2 = (5FA6)16
Dale Roberts
Octal Number System
Octal Number System
Base = 8 or ‘o’ or ‘Oct’
8 symbols: { 0, 1, 2, 3, 4, 5, 6, 7}
Octal to Decimal
(an-1an-2…a1a0)8 = (an-1 x 8n-1 + an-2 x 8n-2 + …+ a1 x 81 + a0 x 80 )10
Example: (127)8 = (1 x 82 + 2 x 81 + 7 x 80 )10 = (64 + 16 + 7)10 = (87)10
Decimal to Octal
Repeated division by 8 (similar in principle to generating binary codes)
Example: (213)10 = (? )8
Divide-by -8
Quotient
Remainder
213 / 8
26 / 8
3/8
26
3
0
5
2
3
Octal digit
Lower digit = 5
Second digit =2
Third digit =3
Stop, since quotient = 0
Hence, (213)10 = (325)8
Dale Roberts
Octal Conversions
Octal to Binary
Expand each octal digit to 3 binary bits.
Example:
(725)8 = (111 | 010 | 101)2
Binary to Octal
Combine every 3 bits into one octal digit
Example:
(110 | 010 | 011)2 = (623)8
Dale Roberts
Practice Exercises
1) Convert the following binary numbers to decimal
numbers:
(a)
0011 B
(b)
0101 B
(c)
0001 0110 B
(d)
0101 0011 B
2) Convert the following decimal numbers to binary:
(a)
21 D
(b)
731 D
(c)
1,023 D
Dale Roberts
Practice Exercises
3)
Convert the following binary numbers to
hexadecimal numbers:
(a)
(b)
(c)
(d)
(a)
(b)
(c)
0011 B
0101 B
0001 0110 B
0101 0011 B
21 D
731 D
1,023 D
4.) Perform the following binary additions and
subtractions. Show your work without using
decimal numbers during conversion.
(a)
(b)
111 B + 101 B
1001 B + 11 B
Dale Roberts
Acknowledgements
These slides where originally prepared by Dr. Jeffrey Huang, updated by Dale
Roberts.
Dale Roberts