Return to Revisions

I ran some benchmarks. I included @JavaDeveloper's original code for comparison, even though it produces erroneous results.

import java.util.Arrays;

public class DivisibilityBenchmark {
    interface DivPredicate {
        boolean isMultiple(int n);
    }

    private static final DivPredicate solJavaDeveloper = new DivPredicate() {
        public boolean isMultiple(int n) {
            if(n < 0) n = -n;

            int evenCtr = 0;
            int oddCtr = 0;

            while (n != 0) {
                if ((n & 1) == 1) { 
                    oddCtr++;
                } 
                n = n>>1;
                if ((n & 1) == 1) {
                    evenCtr++;
                } 
                n = n>>1;
            }

            return evenCtr == oddCtr;
        }
    };

    private static final DivPredicate sol200_success = new DivPredicate() {
        public boolean isMultiple(int n) {
            return n % 3 == 0;
        }
    };

    private static final DivPredicate solSimon = new DivPredicate() {
        public boolean isMultiple(int n) {
            int sum = 0;
            int abs = Math.abs(n);
            if (abs < 10) {
                return abs == 3 || abs == 6 || abs == 9 || abs == 0;
            }
            while (n != 0) {
                sum += n % 10;
                n = n / 10;
            }
            return isMultiple(sum);
        }
    };

    private static final DivPredicate solSupercat = new DivPredicate() {
        public boolean isMultiple(int n) {
            int q = (n >> 20) + ((n >> 10) & 0x3ff) + (n & 0x3ff);
            return q == ((q * 0x5556) >> 16) * 3;
        }
    };

    private static final int table = 0b001001001001001001001001001001001;
    private static final DivPredicate solMaaartinus = new DivPredicate() {
        public boolean isMultiple(int n) {
            int mask = 0x2aaaaaaa;
            int diff = Integer.bitCount(n & mask) - Integer.bitCount(n & ~mask);
            return (table << (diff + 16)) < 0;
        }
    };

    public static boolean[] test(DivPredicate pred, int lower, int upper) {
        boolean[] results = new boolean[upper - lower];
        for (int i = lower; i < upper; i++) {
            results[i - lower] = pred.isMultiple(i);
        }
        return results;
    }

    public static void main(String[] args) {
        // Warm-up and correctness tests
        boolean[] resultJavaDeveloper = test(solJavaDeveloper, -5000, 5000);
        boolean[] result200_success   = test(sol200_success,   -5000, 5000);
        boolean[] resultSimon         = test(solSimon,         -5000, 5000);
        boolean[] resultSupercat      = test(solSupercat,      -5000, 5000);
        boolean[] resultMaaartinus    = test(solMaaartinus,    -5000, 5000);

        if (!Arrays.equals(result200_success, resultJavaDeveloper)) {
            System.out.println("Mismatch JavaDeveloper");
        }
        if (!Arrays.equals(result200_success, resultSimon)) {
            System.out.println("Mismatch Simon André Forsberg");
        }
        if (!Arrays.equals(result200_success, resultSupercat)) {
            System.out.println("Mismatch Supercat");
        }
        if (!Arrays.equals(result200_success, resultMaaartinus)) {
            System.out.println("Mismatch maaartinus");
        }

        // Performance measurement
        int lower = -0x00FFFFFF, upper = 0x00FFFFFF;
        long start, finish;

        start = System.currentTimeMillis();
        resultJavaDeveloper = test(solJavaDeveloper, lower, upper);
        finish = System.currentTimeMillis();
        System.out.printf("Time JavaDeveloper: %d ms\n", finish - start);

        start = System.currentTimeMillis();
        result200_success = test(sol200_success, lower, upper);
        finish = System.currentTimeMillis();
        System.out.printf("Time 200_success: %d ms\n", finish - start);

        start = System.currentTimeMillis();
        resultSimon = test(solSimon, lower, upper);
        finish = System.currentTimeMillis();
        System.out.printf("Time Simon André Forsberg: %d ms\n", finish - start);

        start = System.currentTimeMillis();
        result200_success = test(solSupercat, lower, upper);
        finish = System.currentTimeMillis();
        System.out.printf("Time Supercat: %d ms\n", finish - start);

        start = System.currentTimeMillis();
        result200_success = test(solMaaartinus, lower, upper);
        finish = System.currentTimeMillis();
        System.out.printf("Time maaartinus: %d ms\n", finish - start);
    }
}

Results

Java(TM) SE Runtime Environment (build 1.7.0_45-b18) on OS X 10.9, Intel Core i7 Arrandale 2.66 GHz:

• Mismatch JavaDeveloper
• Time JavaDeveloper: 1160 ms
• Time 200_success: 109 ms
• Time Simon André Forsberg: 1583 ms
• Time Supercat: 260 ms
• Time maaartinus: 262 ms