2.5 Integer Division and Remainder

If both operands of the division operator / are of an integer type, then Java performs integer division. Integer division always results in an integer value?aany fraction in the quotient is simply truncated, or chopped off. We can think of this as rounding down the quotient to the next integer closer to zero, if the quotient isn't already an integer.

The remainder operator % gives the remainder of performing an integer division of its two operands. Given any two integer values m and n,

always equals m. From that, we can deduce the sign of the result of the remainder operation, as shown in Table 2-3 . The sign of the first operand determines the sign of the remainder.

As we mentioned in Section 2.1, the division and remainder operations will throw the ArithmeticException if we attempt to divide by zero.

Suppose the value of n is 13. A straightforward computation would be to multiply the value of x 12 times:

But that involves 12 multiplications. This is not an efficient algorithm whenever the value of n is large.

We can partition 13 into the sum of powers of 2. Because 13 = 8 + 4 + 1,

If we look at 1101, the binary encoding of 13, we can devise a more efficient algorithm. For each bit in the binary encoding of n, we repeatedly square the value of x, and so we compute x ¹ , ( x ¹ ) ² = x ² , ( x ² ) ² = x ⁴ , and ( x ⁴ ) ² = x ⁸ . We then multiply together the power of x corresponding to each 1 bit to give us x ⁸ x ⁴ x ¹ . This involves a total of five multiplications. The savings in multiplications is greater with larger values of n.

Listing 2-3a shows class IntPower with a static method raise() that computes and returns the value of x ⁿ . It is the first of several useful classes that we'll define in the numbercruncher.mathutils package.

Listing 2-3a Class IntPower for doing integer exponentiation.

package numbercruncher.mathutils;

/**
 * Raise a double value to an integer power.
 */
public final class IntPower
{
    /**
     * Compute and return x^power.
     * @param x
     * @param power the integer power
     * @return x^power
     */
    public static double raise(double x, int exponent)
    {
        if (exponent < 0) return 1/raise(x, -exponent);

        double power = 1;

        // Loop to compute x^exponent.
        while (exponent > 0) {

            // Is the rightmost exponent bit a 1?
            if ((exponent & 1) == 1) power *= x;

            // Square x and shift the exponent 1 bit to the right.
            x *= x;
            exponent >>= 1;
        }

        return power;
    }
}

Program 2 C3 is a short program that tests class IntPower by comparing its raise() method to java.lang.Math.pow(). See Listing 2-3b.

Listing 2-3b A test program for class IntPower.

package numbercruncher.program2_3;

import numbercruncher.mathutils.IntPower;

/**
 * PROGRAM 2-3: Test Class IntPower
 *
 * Test the IntPower class.
 */
public class TestIntPower
{
    public static .void main(String args[])
    {
        System.out.println(IntPower.raise(2, 5)   + " " +
                           Math.pow(2, 5));
        System.out.println(IntPower.raise(2, -5)  + " " +
                           Math.pow(2, -5));
        System.out.println(IntPower.raise(2, 0)   + " " +
                           Math.pow(2, 0));
        System.out.println(IntPower.raise(2.5, 5) + " " +
                           Math.pow(2.5, 5));
        System.out.println();
        System.out.println(IntPower.raise(-2, 5)   + " " +
                           Math.pow(-2, 5));
        System.out.println(IntPower.raise(-2, -5)  + " " +
                           Math.pow(-2, -5));
        System.out.println(IntPower.raise(-2, 0)   + " " +
                           Math.pow(-2, 0));
        System.out.println(IntPower.raise(-2.5, 5) + " " +
                           Math.pow(-2.5, 5));
    }
}

Output:

32.0 32.0
0.03125 0.03125
1.0 1.0
97.65625 97.65625

-32.0 -32.0
-0.03125 -0.03125
1.0 1.0
-97.65625 -97.65625