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.