Java's Bytecodes for Logical and Arithmetic Operations

First published in JavaWorld, November 1996

---

Welcome to yet another installment of Under The Hood. This column aims to give Java developers a glimpse of the mysterious mechanisms clicking and whirring beneath their running Java programs. This month's article continues the discussion of the bytecode instruction set of the Java virtual machine (JVM). The article takes a look at integer arithmetic and logic in the JVM, and covers the bytecodes that perform logical and arithmetic operations on integers. Subsequent articles will discuss other members of the bytecode family.

Integer arithmetic
The Java virtual machine offers bytecodes that perform integer arithmetic operations on ints and longs. Values of type byte, short, and char are converted to int before they take part in arithmetic operations. For each bytecode that performs arithmetic on ints, there is a corresponding bytecode that performs the same operation on longs.

All integer types supported by the JVM -- bytes, shorts, ints, and longs -- are signed two's-complement numbers. The two's-complement scheme allows both positive and negative integers to be represented. The most significant bit of a two's-complement number is its sign bit. The sign bit is one for negative numbers and zero for positive numbers and for the number zero.

The number of unique values that can be represented by the two's-complement scheme is two raised to the power of the total number of bits. For example, the short type in Java is a 16-bit signed two's-complement integer. The number of unique integers that can be represented by this scheme is 2¹⁶, or 65,536. Half of the short type's range of values are used to represent zero and positive numbers; the other half of the short type's range are used to represent negative numbers. The range of negative values for a 16-bit two's-complement number is -32,768 (0x8000) to -1 (0xffff). Zero is 0x0000. The range of positive values is one (0x0001) to 32,767 (0x7fff).

Positive numbers are intuitive in that they are merely the base two representation of the number. Negative numbers can be calculated by adding the negative number to two raised to the power of the total number of bits. For example, the total number of bits in a short is 16, so the two's-complement representation of a negative number in the valid range for a short (-32,768 to -1) can be calculated by adding the negative number to 2¹⁶, or 65,536. The two's-complement representation for -1 is 65,536 + (-1) or 65,535 (0xffff). The two's-complement representation for -2 is 65,536 + (-2) or 65,534 (0xfffe).

Addition is performed on two's-complement signed numbers in the same way it would be performed on unsigned binary numbers. The two numbers are added, overflow is ignored, and the result is interpreted as a signed two's-complement number. This will work as long as the result is actually within the range of valid values for the type. For example, to add 4 + (-2), just add 0x0004 and 0xfffe. The result is actually 0x10002, but because there are only 16 bits in a short, the overflow is ignored and the result becomes 0x0002.

Overflow in integer operations does not throw any exception in the JVM. The result is merely truncated to fit into the result type. For example, adding shorts 0x7fff and 1 yields 0x8000. This means that the JVM will report that 32,767 + 1 = -32,768, so long as the values being added are shorts and not ints or longs. It is up to the Java programmer to make sure that the appropriate type -- int or long -- is chosen for integer arithmetic in each situation. (If long isn't long enough, the Java programmer should invent a class that implements really long integers and the operations upon them.) Integer division by zero does throw an ArithmeticException, so the programmer should keep in mind that this exception could be thrown and catch it if necessary.

Exposed int: A Java int reveals its inner nature
The following applet lets you play around with the two's-complement format of integers in the JVM. The Max and Min buttons will give you the maximum and minimum values of the int type. By clicking "Max" followed by "++" you can increment beyond the maximum integer and see what happens. Clicking "Min" followed by "--" lets you decrement beyond the minimum integer. Both of these result in overflow, but no exceptions are thrown by the JVM.

To view the Exposed Int applet (renamed Inner Int), visit the interactive illustrations of Inside the Java Virtual Machine at:

http://www.artima.com/insidejvm/applets/InnerInt.html

Arithmetic opcodes
Integer addition can be performed on ints and longs. Bytes, shorts, and chars are automatically converted to int before they take part in an addition. The following table shows the opcodes that pop the top two values on the stack, add them, and push the result. The type of the values is indicated by the opcode itself, and the result always has the same type as the numbers being added. No exceptions are thrown for any of these opcodes. Overflow is just ignored.

Opcode Operand(s) Description iadd (none) pops two ints, adds them, and pushes the int result ladd (none) pops two longs, adds them, and pushes the long result

The next table shows the exception to the rule that arithmetic opcodes take their operands from the stack. The iinc opcode performs an addition on a local variable of type int. The local variable is indicated by the first byte that follows the iinc instruction in the bytecode stream. The amount to add to the local variable is taken from the second byte following the iinc instruction. The second byte is interpreted as a byte type, an eight-bit signed two's-complement number. The local variable and byte are added, and the result is written back to the local variable. This opcode can be used to change a local variable value by any number between and including -128 through 127. This opcode makes for more efficient incrementing and decrementing of variables that are used to control execution of loops, such as for or while. No exceptions are thrown.

Opcode Operand(s) Description iinc vindex, const adds const to an int at local variable position vindex

Integer subtraction is performed on ints and longs via the following opcodes. Each opcode causes the top two values of the appropriate type to be popped off the stack. The topmost value is subtracted from the value just beneath the topmost value. The result is pushed back onto the stack. No exceptions are thrown by these opcodes.

Opcode Operand(s) Description isub (none) pops two ints, subtracts them, and pushes the int result lsub (none) pops two longs, subtracts them, and pushes the long result

Integer multiplication of ints and longs is accomplished via the following opcodes. Each opcode causes two values of the same type to be popped off the stack and multiplied. The result, of the same type as the numbers being multiplied, is pushed back onto the stack. No exceptions are thrown.

Opcode Operand(s) Description imul (none) pops two ints, multiplies them, and pushes the int result lmul (none) pops two longs, multiplies them, and pushes the long result

The opcodes that perform division on ints and longs are shown in the next table. The division opcodes cause the top two values of the appropriate type to be popped off the stack. The topmost value is divided by the value just beneath the topmost value. The result is pushed onto the stack. Integer division yields a result that is truncated down to the nearest integer value between it and zero. Integer division by zero throws a "/ by 0" ArithmeticException.

Opcode Operand(s) Description idiv (none) pops two ints, divides them, and pushes the int result ldiv (none) pops two longs, divides them, and pushes the long result

The remainder operation is accomplished via the following opcodes on ints and longs. The following opcodes cause the top two values to be popped from the stack. The topmost value is divided by the value just beneath it, and the remainder of that division is pushed back onto the stack. As with the division opcodes, integer remainder by zero throws a "/ by 0" ArithmeticException.

Opcode Operand(s) Description irem (none) pops two ints, divides them, and pushes the int remainder lrem (none) pops two longs, divides them, and pushes the long remainder

The following opcodes perform arithmetic negation on ints and longs. The negation opcodes pop the top value from the stack, negate it, and push the result.

Opcode Operand(s) Description ineg (none) pops an int, negates it, and pushes the result lneg (none) pops a long, negates it, and pushes the result

Logical operands
The JVM's logic capabilities operate on ints and longs. These operations treat ints and longs not as signed two's-complement numbers, necessarily, but more as generic bit patterns. Integer shifting is accomplished via the ishl, ishr, and iushr opcodes. Java's << operator is implemented by ishl. The >> operator is implemented by ishr, and the >>> operator is implemented by iushl. The difference between ishr and iushr is that only ishr does sign extension. The following table shows the instructions that shift ints left and right.

Opcode Operand(s) Description ishl (none) shifts int left ishr (none) arithmetic shifts int right iushr (none) logical shifts int right

The next table shows the instructions that shift longs left and right.

Opcode Operand(s) Description lshl (none) shifts long left lshr (none) arithmetic shifts long right lushr (none) logical shifts long right

The following opcodes perform bitwise logical operations on ints. The opcodes implement Java's &, |, and ^ operators.

Opcode Operand(s) Description iand (none) boolean ands two ints ior (none) boolean ors two ints ixor (none) boolean xors two ints

The next table shows the opcodes that perform bitwise logical operations on longs.

Opcode Operand(s) Description land (none) boolean ands two longs lor (none) boolean ors two longs lxor (none) boolean xors two longs

Logical results: A JVM simulation
The applet below demonstrates a Java virtual machine executing a sequence of bytecodes. The bytecode sequence in the simulation was generated by javac for the incrementLogically() method of the class shown below:

class VulcanCounter {
    void incrementLogically() {
        int spock = 0;
        while (true) {
            int tempSpock = spock;
            for (int i = 0; i < 32; ++i) {
                int mask = 0x1 << i;
                if ((tempSpock & mask) == 0) {
                    tempSpock |= mask;
                    break;
                }
                else {
                    tempSpock &= ~mask;
                }
            }
            spock = tempSpock;
        }
    }
}

The actual bytecodes generated by javac for incrementLogically()
are shown below:

 0 iconst_0 // Push int constant 0.
 1 istore_0 // Pop to local variable 0: int spock = 0;
 2 iconst_0 // Push int constant 0.
 3 istore_1 // Pop to local variable 1: int i = 0;
 4 goto 33 // Jump unconditionally ()
 7 iconst_1 // Push int constant 1.
 8 iload_1 // Push local variable 1 (i).
 9 ishl // Arithmetic shift left top int (i) by next to top int (1).
10 istore_2 // Pop to local variable 2: int mask = i << 0x1;
11 iload_0 // Push local variable 0 (spock).
12 iload_2 // Push local variable 2 (mask).
13 iand // Bitwise AND top two ints: (spock & mask)
14 ifne 24 // Jump if top of stack is not equal to zero: if ((spock & mask) == 0) {
17 iload_0 // Push local variable 0 (spock).
18 iload_2 // Push local variable 2 (mask).
19 ior // Bitwise OR top two ints (spock | mask)
20 istore_0 // Pop to local variable 0: spock |= mask;
21 goto 2 // Jump unconditionally (to top of while): break;
24 iload_0 // Push local variable 0 (spock).
25 iload_2 // Push local variable 2 (mask).
26 iconst_m1 // Push -1.
27 ixor // Bitwise EXCLUSIVE-OR top two ints: ~mask
28 iand // Bitwise AND top two ints: spock & (~mask)
29 istore_0 // Pop to local variable 2: spock &= ~mask;
30 iinc 1 1 // Increment local variable 1 by 1: ++i
33 iload_1 // Push local variable 1 (i).
34 bipush 32 // Push integer constant 32.
36 if_icmplt 7 // Jump (to top of for) if next to top integer is less than top
                     // integer: i < 32
39 goto 2 // Jump unconditionally (to top of while).


The incrementItLogically() method repeatedly increments an int without using the + or ++ operators. Only logical operators &, |, and ~ are used. An increment is accomplished by searching through the bits of the current int, starting with the lowest order bit, and turning ones to zeros. As soon as a one is encountered in the current int, it is changed to zero and the search stops. The resultant int now represents the old int incremented by one. The process is started again on the new int. Each incremented number is stored in the spock variable. Spock is local variable zero in the compiled bytecodes, so you can watch local variable zero count 0, 1, 2, 3, and so on.

To drive the simulation, just press the Step button. Each press of the Step button will cause the JVM to execute one bytecode instruction. To start the simulation over, press the "Reset" button. To cause the JVM to repeatedly execute bytecodes with no further coaxing on your part, press the "Run" button. The JVM will then execute the bytecodes until the Stop button is pressed. The text area at the bottom of the applet describes the next instruction to be executed. Happy clicking.

To view the Logical Results applet, visit the interactive illustrations of Inside the Java Virtual Machine at:

http://www.artima.com/insidejvm/applets/LogicalResults.html

Resources

• "The Java Virtual Machine Specification" is the official word from Sun.
  http://www.javasoft.com/doc/language_vm_specification.html
  (http://java.sun.com/1.0alpha3/doc/vmspec/vmspec_1.html)
• When it comes out, the book The Java Virtual Machine Specification , by Tim Lindholm and Frank Yellin (ISBN 0-201-63452-X), part of The Java Series from Addison-Wesley, will be the definitive JVM reference.
  http://www.aw.com/cp/lindholm-yellin.html
  http://www.aw.com/cp/javaseries.html

This article was first published under the name Under the Hood: Logic and integer arithmetic in JavaWorld, a division of Web Publishing, Inc., November 1996.

Talk back!

Have an opinion? Be the first to post a comment about this article.

About the author

Bill Venners has been writing software professionally for 12 years. Based in Silicon Valley, he provides software consulting and training services under the name Artima Software Company. Over the years he has developed software for the consumer electronics, education, semiconductor, and life insurance industries. He has programmed in many languages on many platforms: assembly language on various microprocessors, C on Unix, C++ on Windows, Java on the Web. He is author of the book: Inside the Java Virtual Machine, published by McGraw-Hill.