CS61B Lecture #11Today:• Integer TypesReadings for Today:Programming Into Java,§5.3,§5.4.Readings for next Topic:Programming Into Java,§4.1Last modified: Fri Nov 30 03:57:45 2001 CS61B: Lecture #11 1Integers• Java has 5 primitive integer types, each with a dif-ferent finite range.• Can characterize by # of bits & signedness:TypeBits Signed?byte 8 Yesshort 16 Yeschar 16 Noint 32 Yeslong 64 Yes• “N bits” means that there are 2Nintegers in thedomain of the type.• If signed, then there are equal numbers of nega-tive and non-negative numbers, and range of valuesis −2N −1.. 2N −1− 1.• If unsigned, there are only non-negative numbers,and range is 0..2N− 1.Last modified: Fri Nov 30 03:57:45 2001 CS61B: Lecture #11 2Integer Literals• Explicit literals for type int, long, char only:int: 123, 0100 /* Octal for 64 */,0x3f /* Hexadecimal for 63 */0xffffffff // Hexadecimal for -1 (!)long: 123L, 2039L, 01000L, 0x3fL,1234567891011Lchar: ’a’’\n’, ’\t’, ’\\’ // newline, tab, \’A’, ’\101’, ’\u0041’ // All equal• No negative literals per se: use negation.• Types byte and short by casting (conversion).Last modified: Fri Nov 30 03:57:45 2001 CS61B: Lecture #11 3Modular Arithmetic• Problem: How do we handle overflow, such as occursin 10000*10000*10000?• Some languages throw an exception (Ada), some giveundefined results (C, C++)• Javadefinesthe result of any arithmetic operationor conversion on integer types to “wrap around”—modular arithmetic.• That is, the “next number” after the largest in aninteger type is the smallest (like “clock arithmetic”).• E.g., (byte) 128 == (byte) (127+1) == (byte) -128• In general,– If the result of some arithmetic subexpression issupposed to have type T , an n-bit integer type,– then we compute the real (mathematical) value, x,– and yield a number, x0, that is in the range of T ,and that is equivalent to x modulo 2n.– (That means that x − x0is a multiple of 2n.)Last modified: Fri Nov 30 03:57:45 2001 CS61B: Lecture #11 4Modular Arithmetic Examples• (byte) (64*8) yields 0, since512 − 0 = 2 · 28.• (byte) (64*2) yields -128, since128 − (−128) = 1 · 28.• (byte) (345*6) yields 22, since2070 − 22 = 8 · 28.• (byte) (-30*13) yields 122, since−390 − 122 = −2 · 28.• (char) (-256*511) yields 256, since−130816 − 256 = −2 · 216.• Fine, but what’sreallygoing on? Why this defini-tion?Last modified: Fri Nov 30 03:57:45 2001 CS61B: Lecture #11 5Modular Arithmetic Under the HoodAnswer: Well, it’s quite natural for a machine thatuses binary (base 2) arithmetic:• For type char,0 = 00000000000000002216− 1 = 11111111111111112• For type byte:0 = 0000000021 = 000000012127 = 011111112−128 = 100000002−1 = 111111112Negative numbers characterized by 1 in leftmostplace: thesign bit.• Terminology: rightmost bit isbit 0, leftmost (in abyte) isbit 7. Hence, changing bit n modifies valueby 2n.Last modified: Fri Nov 30 03:57:45 2001 CS61B: Lecture #11 6Negative numbers• Why this representation for -1?1000000012+ −1111111112= 01|000000002Only 8 bits in a byte, so bit 8 falls off, leaving 0.• The truncated bit is in the 28place, so throwing itaway gives an equal number modulo 28. All bits to theleft of it are likewise divisible by 28.• On unsigned types (char), arithmetic is the same,but we choose to represent only non-negative num-bers modulo 216:100000000000000012+ 216− 1 11111111111111112= 216+ 0 1|00000000000000002Last modified: Fri Nov 30 03:57:45 2001 CS61B: Lecture #11 7Conversion• In general Java will silently convert from one typeto another if this makes sense and no information islost from value.• Otherwise, cast explicitly, as in (byte) x.• Hence, givenbyte aByte; char aChar; short aShort;int anInt; long aLong;// OK:aShort = aByte;anInt = aByte; anInt = aShort; anInt = aChar;aLong = anInt;// Not OK, might lose information:anInt = aLong;aByte = anInt; aChar = anInt; aShort = anInt;aShort = aChar;aChar = aShort; aChar = aByte;// OK by special dispensation:aByte = 13; // 13 is compile-time constantaByte = 12+100 // 112 is compile-time constantLast modified: Fri Nov 30 03:57:45 2001 CS61B: Lecture #11 8Promotion• Arithmetic operations (+, *, . . . )promoteoperandsas needed.• Promotion is just implicit conversion.• For integer operations,– if any operand is long, promote both to long.– otherwise promote both to int.• So,aByte + 3 == (int) aByte + 3 // Type intaLong + 3 == aLong + (long) 3 // Type long’A’ + 2 == (int) ’A’ + 2 // Type intaByte = aByte + 1 // ILLEGAL (why?)• Common example:// Assume aChar is an upper-case letterchar lowerCaseChar= (char) (’a’ + aChar - ’A’); // why cast?Last modified: Fri Nov 30 03:57:45 2001 CS61B: Lecture #11 9Bit twiddling• Java (and C, C++) allow for handling integer types assequences of bits.• No “conversion to bits” needed: they already are.• Operations and their uses:MaskSet Flip Flip all00101100 00101100 00101100& 10100111 | 10100111 ^ 10100111 ~ 1010011100100100 10101111 10001011 01011000• Shifting:Left Arithmetic Right Logical Right10101101 10101101 10101100<< 3 >> 3 >>> 301101000 11110101 00010101• So what is (-1) >>> 29?• In general, left shift by n is multiplication by 2n.• Arithmetic right shift by n is division by 2nroundedtoward−∞.Last modified: Fri Nov 30 03:57:45 2001 CS61B: Lecture #11 10What’s the Use?• Representation technique, especially when space isimportant.• Example: in one long, can store 64 boolean values.class SmallBooleanSet {private long set;boolean get (int k) {return ((set>>>k) & 1) == 1;}void set (int k, boolean val) {set =(set & ~(1 << k)) // clear| ((val ? 1 : 0) << k); // set}}Last modified: Fri Nov 30 03:57:45 2001 CS61B: Lecture #11
View Full Document
Unlocking...