Transcript Number Systems

Number Systems
Number Systems
Prehistory
Unary, or marks: /
/////// = 7
/////// + ////// = /////////////
Grouping lead to Roman Numerals:
VII + V = VVII = XII
Better, Arabic Numerals:
7 + 5 = 12 = 1 x 10 + 2
Arabic Numerals
345 is really




3 x 100 + 4 x 10 + 5 x 1
3 x 102 + 4 x 101 + 5 x 100
3 is the most significant symbol (carries the most
weight)
5 is the least significant symbol (carries the least
weight)
Digits (or symbols) allowed: 0-9
Base (or radix): 10
•Base 10 is a special case of positional number
system
•First used over 4000 years ago in Mesopotamia(Iraq)
•Base 60 (Sexagesimal)
•Digits: 0..59 (written differently)
•5,4560 = 5 x 60 + 45 x 1 = 34510
•Positional number systems a great advance in
mathematics
•Why?
•Try multiplication in (non-positional) Roman numerals(!):
XXXIII (33 in decimal)
XII
(12 in decimal)
--------XXXIII
XXXIII
CCCXXX
----------CCCXXXXXXXXXIIIIII
CCCLXXXXVI
CCCXCVI = 396
•The Mesopotamians wouldn’t have had this problem.
•There are many ways to “represent” a number
•Representation does not affect computation result
LIX + XXXIII = LXXXXII (Roman)
59 + 33
= 92
(Decimal)
•Representation affects difficulty of computing results
•Computers need a representation that works with fast
electronic circuits
Binary:
positional numbers work great with
2-state devices
•Digits (symbols) allowed: 0, 1
•Binary Digits, or bits
•Base (radix): 2
•10012 is really
•1 x 23 + 0 x 22 + 0 X 21 + 1 X 20
•910
•110002 is really
•?
•?
•Computers usually multiply Arabic numerals by converting
to binary, multiplying and converting back (much as us
with Roman numerals)
Octal number system:
Digits (symbols): 0 – 7
Base (radix): 8
3458 is really



3 x 82 + 4 x 81 + 5 x 80
192 + 32 + 5
22910
10018 is really



?
?
?
In C, octal numbers are represented with a
leading 0 (0345 or 01001).
Hexadecimal number system:
Digits (symbols) allowed: 0 – 9, a – f
Base (radix): 16
Hex
Decimal
a
10
b
11
c
12
d
13
e
14
f
15
•A316 is really:
•A x 161 + 3 x 160
•160 + 3
•16310
•3E816 is really:
•3 x 162 + E x 161 + 8 x 160
•3 x 256 + 14 x 16 + 8 x 1
•768 + 224 + 8
•100010
•10C16 is really:
•?
•?
•?
•?
•In C, hex numbers are represented with a leading 0x
(0xa3 or 0x10c).
For any positional number system:
•Base (radix): b
•Digits (symbols): 0..b – 1
•Sn-1Sn-2….S2S1S0
•
Value =
n-1
Σ
(Sibi)
i=0
•Use sum to transform any base to decimal
Decimal  Binary
•Divide decimal value by 2 until the value is 0 (see book)
•Know your powers of two and subtract
… 256 128 64 32 16 8 4 2 1
•Example: 42
•What is the biggest power of two that fits?
•What is the remainder?
•What fits?
•What is the remainder?
•What fits?
What is the binary representation?
Binary  Octal
•Group into 3’s starting at least significant symbol
•Add leading 0’s if needed (why not trailing?)
•Write 1 octal digit for each group
•Example:
100 010 111 (binary)
4
2
7 (octal)
10 101 110 (binary)
2
5
6 (octal)
Octal  Binary
•Write down the 3-bit binary code for each octal digit
Binary  Hex
•Group into 4’s starting al least significant symbol
•Adding leading 0’s if needed
•Write 1 hex digit for each group
•Example:
1001 1110 0111 0000
9
e
7
0
0001
1
1111 1010 0011
f
a
3
Hex  Binary
•Write down the 4 bit binary code for each hex digit
•Example:
3
9
c
8
0011 1001
1100
1000
Hex  Octal
•Do it in 2 steps, hex  binary  octal
Decimal  Hex
•Do it in 2 steps, decimal binaryhex
Why use hex and octal?
Negative Integers
Most humans precede number with “-”
(e.g., -2000)

Accountants, however, use parentheses:
(2000)
Sign-magnitude
Example: -1000 in hex?


100010 = 3 x 162 + e x 161 + 8 x 160
-3E816
Mesopotamians used positional fractions
•Sqrt(2) =
•1.24,51,1060 = 1 x 600 + 24 x 60-1 + 51 x 60-2 +
10 x 60-3
• = 1.414222
•Most accurate approximations until the Renaissance
•What is 3E.8F16?
•How about 10.1012?
f
f
. . . f
f
f .
n-1 n-2
2 1 0
f
f
f
-1 -2 -3
Binary point
2-1
2-2
2-3
2-4
=
=
=
=
.5
.25
.125
.0625
Converting decimal to binary fractions
•Consider left and right of the decimal point separately.
•The stuff to the left can be converted to binary as before.
•Use the following algorithm to convert the fraction:
Fraction
Fraction x 2
Digit left of decimal point
0.8
1.6
1  most significant (f-1)
0.6
1.2
1
0.2
0.4
0
0.4
0.8
0
0.8
(it must repeat
from here!!)
•Different bases have different repeating fractions.
•0.810 = 0.110011001100…2 = 0.11002
•Numbers can repeat in one base and not in another.
What is 2.2 in:
•Binary
•Hex