[SOLVED] Java scheme algorithm Microsoft PowerPoint CSE220 Unit02 Number Systems.pptx

Microsoft PowerPoint CSE220 Unit02 Number Systems.pptx

1

1Kevin McDonnell Stony Brook University CSE 220

CSE 220:

Systems Fundamentals I

Unit 2:

Number Systems

2Kevin McDonnell Stony Brook University CSE 220

Digital Abstraction
Most physical variables are continuous

Temperature
Voltage on a wire
Frequency of an oscillation
Position of a mass

Although voltage, charge and other electrical quantities are
continuous in nature, modern computers are all digital and
work with discrete values

The continuous nature of electricity is abstracted away
and we consider only high and low voltage, or the
presence and absence of electric charge: i.e., 1s and 0s
(bits: binary digits)

3Kevin McDonnell Stony Brook University CSE 220

Binary Digits
So, all data is ultimately represented in a computer in

terms of binary digits
Each bit is either a 0 or a 1

Groups of bits represent larger values
1101 1110 1010 1101 1011 1110 1110 1111
We usually write spaces between groups of four or eight

bits, depending on the situation. More on this soon.

4Kevin McDonnell Stony Brook University CSE 220

Positional Notation
The scheme we use in modern times for representing

numbers is called positional notation
The position of a digit determines how much it contributes

to the numbers value
With decimal (base-10 or radix-10), the place-values are

powers of 10:
, 103, 102, 101, 100, 10-1, 10-2, 10-3,
, 1000s, 100s, 10s, 1s, s, s, s,

642.15really means (6 102) + (4 101) + (2 100) +
(1 10-1) + (5 10-2)

2

5Kevin McDonnell Stony Brook University CSE 220

Positional Notation
More generally, in base-10 notation, the sequence of digits

stands for the polynomial expansion
10 + 10 + + 10 +

10 + 10

We can generalize this to arbitrary bases. In radix-k we use
k distinct symbols (digits), and the place-values are powers
of k.

Radix-2 (binary) notation example:
10101 = 1 2 + 0 2 + 1 2 + 0 2 + 1 2

= 16 + 4 + 1
= 21

When working with multiple radixes, always include a
subscript to identify the radix!

6Kevin McDonnell Stony Brook University CSE 220

Positional Notation
In some circumstances its more natural to write numbers

in base 8, called octal, or base 16, called hexadecimal
With octal there are 8 digits: 0, 1, 2, 3, 4, 5, 6, 7 with place-

values that are powers of 8:
, 83, 82, 81, 80, 8-1, 8-2, 8-3,
, 256s, 64s, 8s, 1s, s, s, s,

376 = 3 8 + 7 8 + (6 8 )

= 192 + 56 + 6
= 254

With hexadecimal we should have 16 digits: 0, 1, 2, 3, 4, 5,
6, 7, 8, 9, A, B, C, D, E, F, where the letters A through F
represent ten through fifteen, respectively

7Kevin McDonnell Stony Brook University CSE 220

Positional Notation
Radix-16 (hexadecimal) notation example:

3E0 = 3 16 + 14 16 + (0 16 )
= 768 + 224 + 0
= 992

Radix-k fractions involve negative powers of k
10.011 = 1 2 + 0 2 + 0 2 +

1 2 + 1 2
= 2 + 0.25 + 0.125
= 2.375

Numbers with terminating decimal representations might
not have terminating representations in other radixes.

For example: 0.2 = 0. 0011

8Kevin McDonnell Stony Brook University CSE 220

Binary, Octal and Hexadecimal
Note that the digits 10

represent the base of a
number in its own base

10 is two
10 is eight
10 is sixteen
10 is ten
Why does it work out like

this?

Binary Octal Hex Decimal
0 0 0 0
1 1 1 1
10 2 2 2
11 3 3 3
100 4 4 4
101 5 5 5
110 6 6 6
111 7 7 7
1000 10 8 8
1001 11 9 9
1010 12 A 10
1011 13 B 11
1100 14 C 12
1101 15 D 13
1110 16 E 14
1111 17 F 15

3

9Kevin McDonnell Stony Brook University CSE 220

Binary Decimal Conversion
Algorithm: Start with initial value of 0. Process bits from

left-to-right order, i.e., from most significant bit (msb) to
least significant bit (lsb)
Double the value from previous step.
Add the next bit value.

10Kevin McDonnell Stony Brook University CSE 220

Binary Decimal Example
Convert 1011100 to decimal (going left to right)

1011100
1
1 2 + 0 = 2
2 2 + 1 = 5
5 2 + 1 = 11
11 2 + 1 = 23
23 2 + 0 = 46
46 2 + 0 = 92

This algorithm will work for any radix. Just multiply by the
radix after each step.

11Kevin McDonnell Stony Brook University CSE 220

Binary Decimal Example
Convert 101011101 to decimal

12Kevin McDonnell Stony Brook University CSE 220

Octal Decimal Example
Convert 417 to decimal

4

13Kevin McDonnell Stony Brook University CSE 220

Decimal Binary Conversion
Algorithm: repeatedly divide the decimal representation by

2, writing the remainders in right-to-left order, i.e., from
least significant bit (lsb) to most significant bit (msb)

Continue dividing until the quotient is 0

14Kevin McDonnell Stony Brook University CSE 220

Decimal Binary Example
Convert 12310 to binary
123 / 2 = 61 rem. 1
61 / 2 = 30 rem. 1
30 / 2 = 15 rem. 0
15 / 2 = 7 rem. 1
7 / 2 = 3 rem. 1
3 / 2 = 1 rem. 1
1 / 2 = 0 rem. 1
Answer: 11110112

15Kevin McDonnell Stony Brook University CSE 220

Decimal Binary Example
Convert 1528 to binary

16Kevin McDonnell Stony Brook University CSE 220

Decimal Hexadecimal Example
The decimal-to-hexadecimal conversion works largely in

the same way, but with division by 16
3241 / 16= 202 rem. 9
202 / 16 = 12 rem. 10
12 / 16 = 0rem. 12
Answer: CA916

This algorithm will also work for any radix. Just divide by
the radix after each step.

5

17Kevin McDonnell Stony Brook University CSE 220

Decimal Octal Example
Convert 1528 to octal

18Kevin McDonnell Stony Brook University CSE 220

Decimal Fractions Binary
Algorithm: generate the bits in left-to-right order, starting

from the radix point:
Multiply the decimal value by 2. If the product is greater

than 1, the next bit is 1. Otherwise, the next bit is 0.
Drop the integer part to get a value less than 1.
Continue until 0 is reached (a terminating expansion) or

a pattern of digits repeats (a non-terminating expansion)
The resulting representation is called fixed-point format

19Kevin McDonnell Stony Brook University CSE 220

Decimal Frac. Binary Example
Convert 0.4 to binary
0.4 2 = 0.80.8 < 1, so write a 0 0.0 0.8 2 = 1.61.6 1, so write a 1 0.01 Drop the integer part 0.6 2 = 1.21.2 1, so write a 1 0.011 Drop the integer part 0.2 2 = 0.4 0.4 < 1, so write a 0 0.0110 Since we arrived at a decimal fraction we have already seen, the pattern will repeat Final answer: 0. 011020Kevin McDonnell Stony Brook University CSE 220Decimal Frac. Binary Example Convert 13.85 to binary621Kevin McDonnell Stony Brook University CSE 220Bin Oct Hex Conversion Because 8 and 16 are powers of 2, converting between bases 2 and 8, and between bases 2 and 16 is very simple Binary Octal Working right-to-left, take bits in groups of 3, converting the groups into octal digits (Why 3? Because 2 = 8. ) Example: 10110101 10 110 101 265 Binary Hexadecimal Working right-to-left, take bits in groups of 4 (a nibble), converting the groups into hexadecimal digits (2= 16) Example: 10110111101 101 1011 1101 5BD Two nibbles = eight bits = one byte22Kevin McDonnell Stony Brook University CSE 220Bin Oct Hex Conversion Octal Binary Working left-to-right, replace each octal digit with its 3-bit binary equivalent Example: 250 010 101 000 10101000 Hexadecimal Binary Working left-to-right, replace each hexadecimal digit with its 4-bit binary equivalent Example: 3FE5 0011 1111 1110 0101 11111111100101 Conversion between octal and hexadecimal is not so straightforward. Its easiest to convert the given representation into binary and then into the desired base.23Kevin McDonnell Stony Brook University CSE 220Bin Oct Hex Conversion Convert 7BA3. BC4 to octal Convert 2713 to hexadecimal24Kevin McDonnell Stony Brook University CSE 220Base Base General algorithm for converting from base 2 to 2 Write out the binary equivalent of the base 2 number and, going right-to-left, form groups of N bits Convert 2713 to base 4 Because 4 = 2 , we will take bits in pairs (right-to-left) General algorithm for converting from base 2 to 2 Write out the binary equivalent of the base 2 number and, going right-to-left, form groups of N bits725Kevin McDonnell Stony Brook University CSE 220General Base Conversions What if we want to convert between two bases other than the ones we’ve studied? Generally it’s easiest to convert the given representation into decimal, and then from decimal into the desired base Example: convert 215 to base 5 215 = 2 7 + 1 7 + 5 7= 98 + 7 + 5= 110 110 / 5 = 22 rem. 0 22 / 5 = 4 rem. 2 4 / 5 = 0 rem. 4 Answer: 215 = 42026Kevin McDonnell Stony Brook University CSE 220Integer Encodings: Unsigned Now we’ll start to see how integers are encoded in hardware In unsigned integer encodings, the numbers 0, 1, 2, , 2 1 are typically encoded as follows:0 000 001 000 012 000 103 000 112 1 111 1127Kevin McDonnell Stony Brook University CSE 220Integer Encodings: Unsigned Binary arithmetic with unsigned integers (particularly, addition), is done in the usual way With decimal addition we can have carried values:Carry values:11 7410+8910Sum: 16310 The same thing can happen with binary additionCarry values: 1 1 1 0 1 0 0 1 0 1 02+ 0 1 0 1 1 0 0 12Sum: 1 0 1 0 0 0 1 1228Kevin McDonnell Stony Brook University CSE 220Binary Addition Example Add the following two 8-bit binary numbers:1 1 0 1 0 1 1 12+ 0 1 0 1 0 0 0 12 We had an overflow. In fixed-precision integer arithmetic, it is possible for an arithmetic operation, such as addition, to result in an overflow. The leftmost carry value is dropped, resulting in an incorrect sum. The programmer must be aware of the range of representable values to avoid unintentional overflow829Kevin McDonnell Stony Brook University CSE 220Integer Encodings: Signed There are several different signed integer encodings which permit the representation of both positive and negative numbers. The hardware designer chooses between the encodings to make the arithmetic hardware simpler or more efficient for certain operations. Sometimes the programmer needs to be aware of what encoding is being used: To format numbers for input or output. To understand the range of representable values and the conditions under which overflow can occur.30Kevin McDonnell Stony Brook University CSE 220Sign/Magnitude Numbers In N-bit sign/magnitude encoding, the most significant bit (leftmost bit) is used as a sign bit (0 = positive, 1 = negative), and the remaining 1 bits represent the magnitude (absolute value) of the number, as in the unsigned scheme. Range: 2 + 1, 2 1 Example (8-bit precision): +75 01001011 15 10001111 Problems with sign/magnitude encoding: Two encodings for zero: +0 and 0 Subtraction is somewhat complicated31Kevin McDonnell Stony Brook University CSE 220Ones Complement Encoding The N-bit ones complement encoding represents integers in the range 2 1 , 2 1 as follows:0 000 00 0 111 111 000 01 1 111 102 000 10 2 111 013 000 11 3 111 00 2 1 011 11 2 1 100 00 To obtain the negative of a value, complement (flip) all the bits: change all 0s to 1s and all 1s to 0s32Kevin McDonnell Stony Brook University CSE 220Ones Complement Encoding Addition may require an end around carry:0 0 0 0 0 1 0 1 5+ 1 1 1 1 1 1 0 0 -31 0 0 0 0 0 0 0 1+ 10 0 0 0 0 0 1 0 2933Kevin McDonnell Stony Brook University CSE 220Ones Complement Example Perform the computation 28 37 in 8-bit one’s complement and convert the result to decimal.34Kevin McDonnell Stony Brook University CSE 220Ones Complement Issue The presence of two representations for zero adds complexity to a circuit that implements addition So we can use a different encoding called twos complement that avoids this problem35Kevin McDonnell Stony Brook University CSE 220Twos Complement Encoding The N-bit twos complement encoding represents integers in the range 2 , 2 1 as follows:0 000 001 000 01 1 111 112 000 10 2 111 103 000 11 3 111 01 2 1 011 11 2 100 0036Kevin McDonnell Stony Brook University CSE 220Twos Complement Encoding To negate a number in twos complement encoding, use one of the following (equivalent) rules:1. Complement all the bits and increment the result.Example: negate 300000011 11111100 111111012. Complement all the bits to the left of the rightmost 1.Example: negate 900001001 11110111 The value 2 has no representation in N-bit twos complement notation, but 2 does.1037Kevin McDonnell Stony Brook University CSE 220Twos Complement What is the 8-bit twos complement representation of 99? What is the decimal equivalent ofthe twos complement number 11001010?38Kevin McDonnell Stony Brook University CSE 220Twos Complement of Zero What happens if we take the twos complement of the number 0 written as an 8-bit number?39Kevin McDonnell Stony Brook University CSE 220The Twos Complement Wheel Unlike mathematical integers, which inhabit a number line, in computer arithmetic the numbers lie on a circle. An overflow occurs when crossing the boundary between the greatest representable positive number and the least representable negative number.Image: users.dickinson.edu/~braught/courses/cs251f02/classes/notes07.html40Kevin McDonnell Stony Brook University CSE 220The Twos Complement Wheel1141Kevin McDonnell Stony Brook University CSE 220Twos Complement Encoding The leftmost bit is the sign bit, which tells whether the number is positive (0) or negative (1). The rightmost bit tells whether the number is even (0) or odd (1). Multiplication by 2 is accomplished by a left shift(introduce 0 at right), dropping the msb:3 611111101 11111010 Division by 2 is accomplished by a right arithmetic shift(replicate sign bit at left), dropping the lsb:6 311111010 1111110142Kevin McDonnell Stony Brook University CSE 220Overflow in Twos Complement In signed arithmetic using twos complement encoding, there is a possibility of overflow, when the correct result is too large or too small to be represented. Overflow cannot occur when adding numbers of opposite sign (or when subtracting numbers of the same sign). Overflow can occur when adding numbers of the same sign (or subtracting numbers of opposite sign).0 1 1 1 1 1 1 0 126+ 0 0 0 0 0 0 1 1 +31 0 0 0 0 0 0 1 -127 The overflow can be detected by noticing that the sum has opposite sign from the addends.43Kevin McDonnell Stony Brook University CSE 220Sign Extension When a twos complement number is extended to more bits, the sign bit must be copied into the most significant bit positions This is called sign-extension Examples: rewrite each of the following numbers (3 and 3) in 8-bit twos complement 3 is 0011 00000011 3 is 1101 1111110144Kevin McDonnell Stony Brook University CSE 220Excess-k Encoding Excess-k encoding is another signed integer encoding that is important due to its use in representing real numbers In excess-k, also called bias-k, integer i is represented by the unsigned encoding of + . For example, in excess-127: 3 is represented as 3 + 127 = 130 10000010 5 is represented as 5 + 127 = 122 01111010 We note that both positive and negative numbers are represented as unsigned values. In excess-127: 127 is 00000000 and +128 is 11111111 The advantage of excess-k notation is that ordering of positive and negative numbers is preserved, which makes comparing two values (e.g., <, >) very straightforward

12

45Kevin McDonnell Stony Brook University CSE 220

Comparison of Integer Encodings
N

decimal
N

binary

sign/mag

1s comp.

2s comp.

bias-127

1 00000001 10000001 11111110 11111111 01111110

2 00000010 10000010 11111101 11111110 01111101

3 00000011 10000011 11111100 11111101 01111100

4 00000100 10000100 11111011 11111100 01111011

5 00000101 10000101 11111010 11111011 01111010

10 00001010 10001010 11110101 11110110 01110101

50 00110010 10110010 11001101 11001110 01001101

90 01011010 11011010 10100101 10100101 00100101

100 01100100 11100100 10011011 10011100 00011011

127 01111111 11111111 10000000 10000001 00000000

128 10000000 N/A N/A 10000000 N/A

46Kevin McDonnell Stony Brook University CSE 220

What About Real Numbers?
We did some base conversions involving real numbers but

havent seen yet how they can be represented in a
computer

A big disadvantage of the so-called fixed-point format or
fixed-precision encoding of such numbers is that they
have a very limited dynamic range
This forma cant represent very large numbers (e.g., 2 )

or very small numbers (e.g., 2 )
These numbers are called fixed point because the

decimal point (or binary point) is fixed, which limits
accuracy

On the other hand, they give exact answers (i.e., no
rounding errors) as long as there is no overflow

47Kevin McDonnell Stony Brook University CSE 220

Floating-Point Format
Because fractions can have non-terminating

representations and/or might require many digits to be
represented exactly, usually real numbers can only be
approximately represented in a computer
We have to tolerate a certain amount of

representational error
The industry standard way used to approximate real

numbers is called floating-point format
IEEE 754 floating-point standard

In this scheme the binary point is allowed to float (i.e., be
repositioned) in order to give as accurate an
approximation as possible

48Kevin McDonnell Stony Brook University CSE 220

IEEE 754 Floating-Point Standard
The IEEE 754 standard species floating-point

representations of numbers and also arithmetic operations
on these representations

IEEE 754 is essentially a form of scientific notation, but
written in binary: 2

This format can be encoded using three fields: a sign bit
(s), an exponent (e) and a fraction (f ), sometimes called
the mantissa

IEEE 754 single-precision format requires 32 bits and
provides about 7 decimal digits of accuracy

IEEE 754 double-precision format requires 64 bits and
provides about 15 decimal digits of accuracy

13

49Kevin McDonnell Stony Brook University CSE 220

IEEE 754 Floating-Point Standard
32-bit version:

64-bit version:

Sign bit: 0(positive) or 1 (negative)
Exponent: stored in excess-127 for the 32-bit version

Excess-1023 for the 64-bit version
Fraction: contains the digits to the right of the binary point

Normalized: the digit to the left of the point is always 1,
and is not represented, giving us one bit of precision for
free

1 bit 8 bits 23 bits

sign exponent fraction (mantissa)

1 bit 11 bits 52 bits

sign exponent fraction (mantissa)

single precision

double precision

50Kevin McDonnell Stony Brook University CSE 220

IEEE 754 to Decimal
Decimal value of a IEEE 754 floating point encoding is

given by the formula: 1 2 1 +
where:
s is the sign bit (0/1).
e is the decimal value of the exponent field
bias is 127 for single-precision, 1023 for double-

precision.
f is the decimal value of the fraction field (regarded as a

binary fraction)

51Kevin McDonnell Stony Brook University CSE 220

IEEE 754 to Decimal Example
What decimal value has the following IEEE 754 encoding?

10111110011000000000000000000000
1 01111100 11000000000000000000000

52Kevin McDonnell Stony Brook University CSE 220

Decimal to IEEE 754 Example
Encode 13.4 in 32-bit IEEE 754 floating-point format

14

53Kevin McDonnell Stony Brook University CSE 220

IEEE 754 Special Values
The smallest 0000 and largest 1111 exponents are

reserved for the encoding of special values:
Zero (two encodings):

= 0 or 1, = 000 0, = 000 0
Infinity:

+: = 0, = 111 1, = 000 0
: = 1, = 111 1, = 000 0

NaN (not a number):
= 0 or 1, = 111 1, = non-zero

Can result from division by zero, 1, log (5), etc.

54Kevin McDonnell Stony Brook University CSE 220

IEEE 754 Format Summary
Property Single-Precision Double-Precision

Bits in Sign 1 1

Bits in Exponent 8 11

Bits in Fraction 23 52

Total Bits 32 64

Exponent Encoding excess-127 excess-1023

Exponent Range 126 to 127 1022 to 1023

Decimal Range 10 to 10 10 to 10

55Kevin McDonnell Stony Brook University CSE 220

Floating-Point Limitations
There are ~2 different values that can be represented in

single-precision floating point.
This is the same as the number of values that can be

represented using 32-bit integer encodings.
Many values (even integers) do not have floating-point

representations:
Examples: 33554431 and 0.33554431

Try assigning these to a float variable in Java and then
printing them out.

Caution: Results of floating point calculations are not exact.
Never use floating point when exact results are essential or

in equality checks, such as in conditional statements