UnsignedDivision.java

Below is the syntax highlighted version of UnsignedDivision.java from §6.1 Data Representations.

/******************************************************************************
 *  Compilation:  javac UnsignedDivision.java
 *  Execution:    java UnsignedDivision a b
 *
 *  Compute a / b and a % b as if a and b were unsigned 32 bit
 *  integers.
 *     - By converting to long integers
 *     - By direct calculation using shift, add, substract, compare
 *
 *
 ******************************************************************************/

import java.util.Random;

public class UnsignedDivision {

    // unsigned division and remainder by casting to long
    public static int div1(int num, int den) {
        long MASK = (1L << 32) - 1;   // 0x00000000FFFFFFFF;
        return (int) ((num & MASK) / (den & MASK));
    }
    public static int rem1(int num, int den) {
        long MASK = (1L << 32) - 1;   // 0x00000000FFFFFFFF;
        return (int) ((num & MASK) % (den & MASK));
    }

    // is a >= b when viewed as unsigned int
    public static boolean geq(int a, int b) {
        if (b < 0 && a >= 0) return false;
        if (a < 0 && b >= 0) return true;
        return a >= b;
    }

    // unsigned division and remainder
    // Reference: http://www.cise.ufl.edu/~mssz/CompOrg/CDA-arith.html
    public static int div2(int num, int den) {
        if (den == 0) throw new ArithmeticException("/ by zero");
        int q = num;   // quotient
        int r = 0;     // remainder
        for (int i = 0; i < 32; i++) {
            r <<= 1;
            if (q < 0) r++;
            q <<= 1;
            if (geq(r, den)) {   // important to do comparison as if they're unsigned
                q++;
                r -= den;
            }
        }
        return q;
    }

    public static int rem2(int num, int den) {
        if (den == 0) throw new ArithmeticException("/ by zero");
        int q = num;   // quotient
        int r = 0;     // remainder
        for (int i = 0; i < 32; i++) {
            r <<= 1;
            if (q < 0) r++;
            q <<= 1;
            if (geq(r, den)) {   // important to do comparison as if they're unsigned
                q++;
                r -= den;
            }
        }
        return r;
    }


    public static void main(String[] args) {
        Random rand = new Random();
        int a = rand.nextInt();
        int b = rand.nextInt();
        int n = 0;
        while ((div1(a, b) == div2(a, b)) && (rem1(a, b) == rem2(a, b))) {
            do {
                a = rand.nextInt();
                b = rand.nextInt();
            } while (b == 0);
            n++;
        }
        StdOut.println(n);

        StdOut.println("Signed:    " + a + " / " + b + " = " + (a / b));
        StdOut.println("Signed:    " + a + " % " + b + " = " + (a % b));

        StdOut.println("Unsigned:  " + a + " / " + b + " = " + div1(a, b));
        StdOut.println("Unsigned:  " + a + " % " + b + " = " + rem1(a, b));
        StdOut.println("Unsigned:  " + a + " / " + b + " = " + div2(a, b));
        StdOut.println("Unsigned:  " + a + " % " + b + " = " + rem2(a, b));
    }

}