CS计算机代考程序代写 Java PowerPoint Presentation

PowerPoint Presentation

Slide #27 of 46

No of

Bits

Min

(Binary)

Max

(Binary)

Max

(Decimal)

1 0 1 1

2 00 11 3

3 000 111 7

4 0000 1111 15

8 00000000 11111111 255

n 0…0 (n bits) 1…1 (n bits) 2n – 1

Bits and Numbers (Unsigned)

Slide #28 of 46

Binary

Value

Value

(Exact)

Value

(Approx)

Equivalent

(Decimal)

210 1024 1000

(one thousand)

103

(Kilo k)

220 1048576 1000000

(one million)

106

(Mega M)

230 1073741824 1000000000

(one billion)

109

(Giga G)

240 1099511628000 1000000000000

(one trillion)

1012

(Tera T)

Approximating Big Powers of 2

 What is the value of “K”, “M”, and “G”?

 In computing, particularly w.r.t. memory, the base-2

interpretation generally applies (Column 2)

Slide #29 of 46

In the lab…

1. Double click on My Computer

2. Right click on C:

3. Click on Properties

/ 230 =

Example – Memory Space

Slide #30 of 46

What is Overflow?

What is the highest value that can be stored in 8-

bits? And what happens when arithmetic goes

outside the storable range?

Example: 255 + 1 in 8 bits ?

1111 1111 = 255

0000 0001 = 1

1 0000 0000 0

Overflow bit gets

lost

Answer seems

like Zero

Slide #31 of 46

What is Overflow?

 In a given type of computer, the size of integers is a

fixed number of bits.

32 or 64 bits are popular choices these days.

 It is possible that addition of two n bit numbers yields

a result requiring n+1 bits.

Overflow is the term for an operation whose results

exceed the space allocated for a number.

Slide #32 of 46

Negative Numbers

 In 8-bit arithmetic 255 + 1 looks like 0, 255 is

behaving like -1

11111111 is two’s complement representation of -1

More generally, for 2’s complement representation

(in 8 bits) of a -ve number -X; we can use ordinary

binary representation of 256 – X

Even more generally, the 2’s complement of -X, we

can use the following formula: 2n – X

 Where n is the number of bits

Slide #33 of 46

Finding 2’s Complement – General Method

Flip all of the bits

Add 1

Example: How to represent -20 in 2’s complement?

20 in binary 00010100

Flip All Bits 11101011

Add 1 11101100

256 – X = 255 – X + 1

(still 8 bits)

255 – X = Flip All Bits of X

Works in any

number of bits

Slide #34 of 46

8-bit Signed Integers

 Integers in the range -128 … +127

127 01111111

… …

1 00000001

0 00000000

-1 11111111

-2 11111110

… …

-128 10000000

2’s complement

MSB shows sign:

0 for non-negative (zero or positive)

1 for negative numbers

Slide #35 of 46

Range for n-bit Signed Integers

In general for signed integers: -2n-1 … 2n-1-1

 For Example:

For un-signed integers: 0 … 2n-1

Bits Minimum Maximum

8 -128 +127

16 -32768 +32767

32 -2147483648 +2147483647

Bits Minimum Maximum

8 0 255

16 0 65535

32 0 4294967295

Slide #36 of 46

Binary Numbers: How they should be treated?

For much of the arithmetic (+, -, *) it does not matter

For comparisons, need to know whether the

numbers are signed or unsigned:

For Example:

signed -1 < 0 TRUE unsigned 255 < 0 FALSE Slide #37 of 46 Integer Numbers – Behavior in Java For integer (whole number) arithmetic: values are treated as signed bits beyond storable range are lost overflow ignored - no errors flagged! Data Types byte short int long Bytes 1 2 4 8 Bits 8 16 32 64 A boolean value (true or false) is 1 bit (1 or 0) Slide #38 of 46 Integer Numbers – Sign Extension  Sometimes you extend a number by giving it more space. For unsigned arithmetic: just provide extra 0s e.g. extending 8 to 16 unsigned: provide 0s For signed arithmetic: use sign extension MSB is repeated Java uses sign extension when converting byte to short (and short to int, int to long) 11111111 1111111100000000 11111111 1111111111111111 Slide #39 of 46 Selecting Appropriate Data Types Make sure your datatype is big enough for the numbers you want to compute with! e.g. int for money in pence may be too short max int = 231 – 1 = 2 x (210)3 – 1 ≈ 2 x 109 pence = £ 2 x 107 = £ 20 million If amounts go above that, can use long - or BigInteger int = 4 bytes = 32 bits unsigned, max = 232 – 1 but int is signed 210 = 1024 ≈ 103 Slide #40 of 46 How quickly overflow can occur? n factorial (n!) = n * (n – 1) * (n – 2) * … * 1 public static void main(String[] args) { for (int i = 6; i < 20; i++){ System.out.println(""+i+", "+fact(i)); } } /** * Calculate factorial. * requires: 0 <= n * @param n number whose factorial is to be calculated * @return factorial of n */ public static int fact(int n){ int a = 1; for (int i = 1; i <= n; i++){ a = a * i; } return a; } "requires" comment says nothing is guaranteed if n < 0 n, n! 6, 720 7, 5040 8, 40320 9, 362880 10, 3628800 11, 39916800 12, 479001600 13, 1932053504 14, 1278945280 15, 2004310016 16, 2004189184 17, -288522240 18, -898433024 19, 109641728 Do you see any problems? Slide #41 of 46 How quickly overflow can occur? n, n! 6, 720 7, 5040 8, 40320 9, 362880 10, 3628800 11, 39916800 12, 479001600 13, 1932053504 14, 1278945280 15, 2004310016 16, 2004189184 17, -288522240 18, -898433024 19, 109641728 Obviously wrong for n = 17 or 18 - negative answers Actually, all answers from n = 13 must be wrong n! = n * (n-1) * ... * 10 * ... * 5 * ... * 2 * 1 10x5x2 = 100 - correct answer must end 00 for n = 10 or more At n = 13 get overflow. After that all the answers are wrong. A rough calculation explains why n = 13 is where it goes wrong. 12! = 479,001,600 ≈ 4.79 x 108 13! = 6,227,020,800 ≈ 6.23 x 109 Max int = 231 – 1 = 2,147,483,647 ≈ 2.15 x 109 13! is too big for int (signed 32-bit integer) Slide #42 of 46 A Slightly Better Version! public static void main(String[] args) { for (int i = 6; i < 20; i++){ System.out.println(""+i+", "+fact(i)); } } /** * Calculate factorial. * requires: 0 <= n <= 12 * @param n number whose factorial is to be calculated * @return factorial of n */ public static int fact(int n){ int a = 1; for (int i = 1; i <= n; i++){ a = a * i; } return a; } Alternatively: Use long (but still overflow) Use BigInteger Slide #43 of 46 Long Version! /** * Calculate factorial. * requires: 0 <= n <= 20 * @param n number whose factorial is to be calculated * @return factorial of n */ public static long lfact(int n){ long a = 1; for (int i = 1; i <= n; i++){ a = a * i; } return a; } Works up to n = 20 n, n! 6, 720 7, 5040 8, 40320 9, 362880 10, 3628800 11, 39916800 12, 479001600 13, 6227020800 14, 87178291200 15, 1307674368000 16, 20922789888000 17, 355687428096000 18, 6402373705728000 19, 121645100408832000 20, 2432902008176640000 21, -4249290049419214848 Slide #44 of 46 Summary Representing numbers in the computer Whole numbers in binary, octal, decimal and hexadecimal notations  Converting from one representation to another  Representing negative numbers  Overflow and its consequences.