Transcript Base Conversion

PSU CS 106
Computing Fundamentals II
Base Conversion
of
Integer Numbers
HM 4/6/2008
Agenda
•
•
•
•
•
•
General Conversion Algorithm
Digits for Numbers with Base b
Power-Series Conversion
Decimal to Binary Samples
Binary to Decimal Samples
Simplest Conversions
© Dr. Herbert G. Mayer
2
General Conversion Algorithm
• The general algorithm for converting a non-negative number
N of base b = 10 to a number T of same value but different
base t, with t being an integer
• Summary:
– Repeatedly divide N by t and record the remainders modulo t
– New number T is the sequence of the remainder digits in reverse order
of creation
• Detail of Algorithm:
– This method uses repeated integer division of N by t:
– Starting with the absolute value of N, set the initial quotient q = N:
– Step 1: perform the next integer division, create the quotient q = q / t,
and record the remainder in the range 0 .. t-1
– Step 2: Is q = 0? If so, go to step 4
– Step 3: Else repeat step 1
– Step 4: record the remainders from bottom-to-top in left-to-right order.
That is the new number T
© Dr. Herbert G. Mayer
3
General Conversion Algorithm
• Example: Convert decimal N = 500 to an equivalent number T of
base t = 2:
N base 10
Quotient N / 10
repeated
Remainder
base 2
500 / 2 =
250
0
250 / 2 =
125
0
125 / 2 =
62
1
62 / 2 =
31
0
31 / 2 =
15
1
15 / 2 =
7
1
7 / 2 =
3
1
3 / 2 =
1
1
1 / 2 =
0
1
STOP
Binary representation of decimal 500 is 111110100
© Dr. Herbert G. Mayer
4
Digits for Numbers with Base b
Digits for Numbers with base b are explained here:
• Any plausible numeric system using a power-series similar to the
decimal system should have a base b > 1. Consequently there may
be a need for new digits.
• In the decimal system we use the digits ‘0’ .. ‘9’.
• If a base b > 10 is chosen, a typical convention is to use additional
digits from the Roman alphabet, with digit ‘a’ standing for the value
10, ‘b’ for the value 11 etc.
• Interestingly, the Babylonian system with base 60 did not use that
convention. Instead, this system created 60 different digits via a
combination of distinct digits (like the 10 decimal digits) and
repetition (like the Roman system, that lists 3 ‘X’ for decimal 30).
• In the hexadecimal system (base b = 16) the convention is to use
letters ‘a’ .. ‘f’ for the digits values 10 through 15. Lower- and
upper-case letters are used synonymously for convenience.
© Dr. Herbert G. Mayer
5
Digits for Numbers with Base b=16
Hexadecimal digit
Equivalent decimal values
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
A
10
B
11
C
12
D
13
E
14
F
15
© Dr. Herbert G. Mayer
6
Digits for Numbers with Base b=16
• Example 1:
– symbol 3ba8 is a possible hexadecimal number. The highest
power of 16 used in 3ba8 is in the position associated with hex
digit ‘3’. Its corresponding numeric value is 163, which is 4,096
in decimal. Thus hex digit ‘3’ contributes 3 * 4096 to the total
value of the number. The ‘b’ contributes 11 * 162, etc.
• Example 2:
– 0A01_FFFF is a possible hexadecimal number. The highest power
of 16 used in this hex number is the one in the position
associated with digit ‘A’. Its corresponding numeric value is 166
= 16,777,216 in decimal.
– Thus hex digit ‘A’ contributes 10 * 16,777,276 to the total value
of number 0A01_FFFF. It could also be written as: a01fff.
For numeric systems with bases b < 10 there is no need to invent new
digits. A subset of the 10 decimal digits can be used.
© Dr. Herbert G. Mayer
7
Digits for Numbers with Base b=20
Should we chose the base b = 20, we’d have to invent 4 more digits.
Adding ‘g’ to ‘j’ to hex digits might be plausible, shown below.
© Dr. Herbert G. Mayer
Base 20 digits
Equivalent decimal
values
0
0
1 .. 8
1 .. 8
9
9
A
10
B
11
C
12
D
13
E
14
F
15
G
16
H
17
I
18
J
19
8
Power-Series Conversion
• General power-series conversion of a number T with a base
different from 10 to an equivalent number N with base b = 10.
• Summary:
– Starting with an initial decimal value of 0, for all digits d of T, multiply d by
the corresponding power of t, and add to the total decimal result.
• Detail:
– Starting with an initial total value of 0, the initial exponent e = 0 for base t,
and the rightmost digit d0 of T, do the following:
– Step 1: set the exponent e = 0, and the total decimal value total = 0
– Step 2: compute te, multiply de by te and add to total
– Step 3: increase e by 1
– Step 4: move to the next higher digit d if one is left, and execute step 2;
else go to step 5
– Step 5: we are done, all digits have been taken into account, and the
decimal value is in total.
© Dr. Herbert G. Mayer
9
Power-Series Conversion
• Example for base 2: binary number 0100010 is to be
converted to decimal:
– Tracking the exponents e for the powers of 2 in 100010, there are only
2 contributing binary digits different from 0.
– Ignore leading zeros; there is one leading 0
– These 1 digits are at exponents e=1 and e=5
– I.e. 1 * 21 which is 2, and 1 * 25 which is 32.
– Hence the total is 2 + 32 = 34.
• Example for base 16: hexadecimal number 1ba0 is
converted to base 10:
– Tracking the exponents e for the powers of 16, we see, that there are
only 3 contributing hex digits different from 0.
– These are at powers 1, 2, and 3
• a16 * 161 = a16 * 16
= 10 * 16
• b16 * 162 = b16 * 256 = 11 * 256, and
• 116 * 163 = 116 * 4096 = 4096.
– Hence the total = 10 * 16 + 11 * 256 + 1 * 4096 = 7072.
© Dr. Herbert G. Mayer
10
Decimal to Binary Samples
Algorithmic base conversion works for target base > 10 and < 10.
Decimal N
Quotient N / 2
Remainder
678 / 2 =
339
0
339 / 2 =
169
1
169 / 2 =
84
1
84 / 2 =
42
0
42 / 2 =
21
0
21 / 2 =
10
1
10 / 2 =
5
0
5/2=
2
1
2/2=
1
0
1/2=
0
1
STOP
Binary representation of decimal 678 is 1010100110
© Dr. Herbert G. Mayer
11
Decimal to Hexadecimal Samples
N = 500 base 10
Quotient N / 16 repeated
Remainder base 16
Written in base 10 and 16
500 / 16 =
31
4 =4
31 / 16 =
1
15 = f
1 / 16 =
0
1 =1
STOP
Hexadecimal representation of decimal 50010 is 1f416
© Dr. Herbert G. Mayer
12
Decimal to Hexadecimal Samples
N = 1678 base 10
Quotient N / 16 repeated
Remainder base 16
1678 / 16 =
104
14 = e
104 / 16 =
6
8=8
6 / 16 =
0
6=6
STOP
Hexadecimal representation of decimal 1,67810 is 68e16
© Dr. Herbert G. Mayer
13
Binary to Decimal Samples
• Binary number 10001011 converted to decimal, using powerseries:
–
–
–
–
1
1
1
1
*
*
*
*
20
21
23
27
=
1+
=
2+
=
8+
= 128 +
Decimal representation binary 100010112 is 13910
• Binary number 100001010 converted to decimal, using powerseries:
– 1 * 21 =
1+
– 1 * 23 =
2+
– 1 * 28 = 256 +
Decimal representation binary 1000010102 is 25910
© Dr. Herbert G. Mayer
14
Simplest Conversions
• Conversion from source base bs to target bt are trivial, whenever
one is an integral power of the other
• This is the case between source base bs = 16 to target base bt = 2
• Also between bases bs = 16 and bt = 4
• Also between bases bs = 16 and bt = 8
• Also between bases bs = 4 and bt = 2
• Etc.
• It is easy to see that in such cases the conversion via numeric
computation can be by-passed altogether
• Instead, the conversion amounts to simply re-writing the digits in
expanded or contracted form
• For example, the hex number 1f16 rewritten in binary is 111112
© Dr. Herbert G. Mayer
15
Simplest Conversions
Decimal value
Decimal value
Binary number
Base 4 equivalent
584
1001001000
21020
4096
1000000000000
1000000
4_096
1_00_00_00_00_00_00
1000000
Binary number
Hexadecimal equivalent
584
1001001000 = 10_0100_1000
248
4096
1_0000_0000_0000 = 1000000000000
1000
Decimal value
Hexadecimal number
Binary equivalent
65,535
FFFF
1111_1111_1111_1111
4,294,967,295
FFFF_FFFF
1111_1111_1111_1111_1111_1111_1111_1111
2,748
ABC
1010_1011_1100
500
1F4
1_1111_0100
© Dr. Herbert G. Mayer
16