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 {
    static abstract class DivPredicate {
        private final String name;

        public DivPredicate(String name) {
            this.name = name;
        }

        public abstract boolean isMultiple(int n);
    }

    private static final long MAAARTINUS_TABLE = 0x9249249249240000L;
    // = 0b1001001001001001001001001001001001001001001001000000000000000000L;

    private static final DivPredicate[] SOLUTIONS = new DivPredicate[] {
        new DivPredicate("200_success") {
            public boolean isMultiple(int n) {
                return n % 3 == 0;
            }
        },

        new DivPredicate("JavaDeveloper") {
            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;
            }
        },

        new DivPredicate("Simon André Forsberg") {
            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);
            }
        },

        new DivPredicate("supercat Rev 2") {
            public boolean isMultiple(int n) {
                int q = (n >> 20) + ((n >> 10) & 0x3ff) + (n & 0x3ff);
                return q == ((q * 0x5556) >> 16) * 3;
            }
        },

        new DivPredicate("supercat Rev 4") {
            public boolean isMultiple(int n) {
                if (n < 0) n = -n;
                int q = (int)((n * 0x55555556L) >> 32);
                n = n - q - q - q;
                return n == 0;
            }
        },

        new DivPredicate("maartinus Rev 4") {
            public boolean isMultiple(int x) {
                int diff = Integer.bitCount(x & 0x2AAAAAAA) + Integer.bitCount(x);
                return (MAAARTINUS_TABLE << diff) < 0;
            }
        }
    };

    public static boolean[] run(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 int perf(DivPredicate pred, int lower, int upper) {
        int count = 0;
        for (int i = lower; i < upper; i++) {
            if (pred.isMultiple(i)) {   // Count results to ensure that the
                count++;                // work is not optimized away
            }
        }
        return count;
    }

    public static void main(String[] args) {
        // Warm-up and correctness tests
        boolean[] expected = null;
        for (DivPredicate pred : SOLUTIONS) {
            boolean[] actual = run(pred, -5000, 5000);
            if (expected == null) {
                expected = actual;
            } else if (!Arrays.equals(expected, actual)) {
                System.out.println("Mismatch " + pred.name);
            }
        }

        // Performance measurement
        final int LOWER = -0x00FFFFFF, UPPER = 0x00FFFFFF;
        for (DivPredicate pred : SOLUTIONS) {
            long start = System.currentTimeMillis();
            perf(pred, LOWER, UPPER);
            long finish = System.currentTimeMillis();
            System.out.printf("Time %s: %d ms\n", pred.name, finish - start);
        }
    }
}

Results

Java(TM) SE Runtime Environment (build 1.7.0_45-b18) on OS X 10.9, Intel Core i7-2600 Sandy Bridge 3.4 GHz:

• Mismatch JavaDeveloper
• Time 200_success: 63 ms
• Time JavaDeveloper: 1020 ms
• Time Simon André Forsberg: 1157 ms
• Time supercat Rev 2: 140 ms
• Time supercat Rev 4: 136 ms
• Time maaartinus Rev 4: 139 ms