UNIVERSITY OF CALIFORNIADepartment of Electrical Engineeringand Computer SciencesComputer Science DivisionCS61B P. N. HilfingerSpring 1998Numbers1 IntegersThe Scheme language has a notion of integer data type that is particularly convenient for theprogrammer: Scheme integers correspond directly to mathematical integers and there are stan-dard functions that correspond to the standard arithmetic operations on mathematical integers.While convenient for the programmer, this causes headaches for those who have to implementthe language. Computer hardware has no built-in data type that corresponds directly to the math-ematical integers, and the language implementor must build such a type out of more primitivecomponents.Historically, therefore, most “traditional” programming languages don’t provide full mathe-maticalintegerseither,butinsteadgiveprogrammerssomethingthatcorrespondstothehardware’sbuilt-in data types. As a result, what passes for integer arithmetic in these languages is at leastquite fast. What I call “traditional” languages include FORTRAN, the Algol dialects, Pascal, C,C++, Java, Basic, and many others. Here, I will discuss the integer types provided by Java, whichis in many ways typical.2 Modular arithmeticThe integral values in Java differ from the mathematical integers in that they come from a finiteset (or domain). Specifically, the five integer types have the ranges shown in Table 1. With alimited range, the question that naturally arises is what happens when an arithmetic result fallsoutside this range (overflows). For example, what is the result of 1000000*10000, in whichthe two operands are both of type int?105Numbers106Type Modulus Minimum Maximumlong 2642632631( 9223372036854775808) (9223372036854775807)int 2322312311( 2147483648) (2147483647)short 2162152151( 32768) (32767)byte 2827271( 128) (127)char 2160 21610 (65535)Table 1: Ranges of values of Java integral types. Values of a type represented with bits arecomputed modulo 2 (the “Modulus” column).Computer hardware, in fact, answers this question in various ways, and as a result, traditionallanguages prior to Java tended to finesse this question, saying that operations producing an out-of-range result were “erroneous,” or had “undefined” or “implementation-dependent” results. Infact, they also tended to finesse the question of the range of various integer types; in standardC, for example, the type int has at least the range of Java’s type short, but may have more.To do otherwise than this could make programs slower on some machines than they would be ifthe language allowed compilers more choice in what results to produce. The designers of Java,however, decided to ignore any possible speed penalty in order to avoid the substantial hasslescaused by the fact that differences in the behavior of integers from one machine to anothercomplicate the problem of writing programs that run on more than one type of machine.Javasolvestheoverflowquestionby sayingthat integerarithmeticismodular. In mathematics,we say that two numbers are identical “modulo ” if they differ by a multiple of :mod iff there is an integer, , such thatThe numeric types in Java are all computed modulo some power of 2. Thus, the type shortis computed modulo 216. Any attempt to convert an integral value, , to type short gives avalue that is equal to modulo 216. There is an infinity of such values; the one chosen is the onethat lies between 215and 2151, inclusive. For example, converting the values 256, 0, and1000 to type short simply give 256, 0, and 1000, while converting 32768 (which is 215) totype short gives 32768 (because 32768 32768 216) and converting 131073 to typeshort gives 1 (because 1 131073 2 216).It may occur to you from this last example that converting to type short looks like takingthe remainder of when divided by 216(or, as it would be written in Java, ‘x % 65536’). Thisis almost true. In Java, division of integers, as in x / y, is defined to yield the result of theNumbers107mathematical division with the remainder discarded. Thus, in Java, 3 and3. Remainder on integer operands is then defined by the equationx%y x - (x/y)*ywhere ‘/’ means Java-style division of integers. Thus, in Java, 11%3 11% 3 2 and11%3 11% 3 2. However, to use an example from above, 32768%65536 is just32768 back again, and one has to subtract 21665536 to get the right short value. It is correctto say that converting to type short is like taking the remainder from dividing by 216andsubtracting 216if the result is 215.For addition, subtraction, and multiplication, it doesn’t matter at what point you perform aconversion to the type of result you are after. This is an extremely important property of modulararithmetic. For example, considerthe computation527 * 1000 + 600, where the final resultis supposed to be a byte (range 128 to 127, modulo 256 arithmetic). Doing the conversion atthe last moment gives527 1000 600 527600 16 mod 256;or we can first convert all the numerals to bytes:15 24 88 272 16 mod 256;or we can convert the result of the multiplication first:527000 600 152 88 240 16 mod 256We always get the same result in the end.Unfortunately, this happy property breaks down for division. For example, the result ofconverting 256 7 to a byte (36) is not the same as that of converting 0 7 to a byte (0), eventhough both 256 and 0 are equivalent as bytes (i.e., modulo 256). Therefore, we have to be alittle bit specific about exactly when conversions happen during the computation of an expressioninvolving integer quantities. The rule is:To compute , where is any of the Java operations +, -, *, /, or %, andand are integer quantities (of type long, int, short, char, or byte),If either operand has type long, compute the mathematical result converted totype long.Otherwise, compute the mathematical result converted to type int.By “mathematical result,” I mean the result as in normal arithmetic, where ‘/’ is understood tothrow away any remainder.So, for example, considerNumbers108short x = 32767;byte y = (byte) (x * x * x / 15);The notation ‘( ) ’ is called a cast; it means “ converted to type ” The cast constructhas higher precedence than arithmetic operations, so that (byte)x*x*x would have meant((byte)x)*x*x. According to the rules, y is computed asshort x = 32767;byte y = (byte) ((int) ((int) (x*x) * x) / 15);The computation proceeds:x*x --> 1073676289(int) 1073676289 --> 10736762891073676289 * x -->
View Full Document
Unlocking...