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("canonical") {
            public boolean isMultiple(int n) {
                return n % 3 == 0;
            }
        },

        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;
            }
        },

        new DivPredicate("200_success (bis)") {
            public boolean isMultiple(int n) {
                return n % 3 == 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);
        }
        for (int i = SOLUTIONS.length - 1; i >= 0; i--) {
            DivPredicate pred = SOLUTIONS[i];
            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 canonical: 62 ms (← Grossly unfair advantage!)
• Time 200_success: 79 ms (Still unreliable!)
• Time JavaDeveloper: 995 ms
• Time Simon André Forsberg: 1146 ms
• Time supercat Rev 2: 151 ms
• Time supercat Rev 4: 146 ms
• Time maartinus Rev 4: 142 ms
• Time 200_success (bis): 146 ms (← Probably a fair comparison)
• Time 200_success (bis): 146 ms
• Time maartinus Rev 4: 140 ms
• Time supercat Rev 4: 146 ms
• Time supercat Rev 2: 153 ms
• Time Simon André Forsberg: 1168 ms
• Time JavaDeveloper: 1029 ms
• Time 200_success: 143 ms
• Time canonical: 144 ms

Discussion

As @maaartinus points out, the first three solutions in this benchmark receive an unfair advantage due to monomorphic inline caching or other JIT optimizations. To illustrate how the benchmark was flawed, I've included the same solution three times (as "canonical", "200_success", and "200_success (bis)"), then executed the tests in reverse order for good measure. I'll take this as a lesson to use a proper benchmarking tool such as Caliper.

Based on the revised measurements, I would draw the conclusion that solutions by @200_success, @supercat, and @maaartinus are nearly identical in performance.