Efficiently checking if a number is divisible by 3

Question

I'm looking for code review, best practices and optimizations.

public final class DivThreeEfficiently {

    private DivThreeEfficiently() {}

    /**
     * Returns true if the input number is divisible by three. 
     * Else returns false.
     * 
     * @param n     the input number
     * @return      true if input number is divisible by three
     */
    public static boolean isMultipleOfThree(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;
    }   
}

public class DivThreeEfficientlyTest {

    @Test
    public void testEvenNegative() {
        assertTrue(DivThreeEfficiently.isMultipleOfThree(-3));
        assertTrue(DivThreeEfficiently.isMultipleOfThree(-6));
        assertTrue(DivThreeEfficiently.isMultipleOfThree(-12));
    }

    @Test
    public void testEvenPositive() {
        assertTrue(DivThreeEfficiently.isMultipleOfThree(0));
        assertTrue(DivThreeEfficiently.isMultipleOfThree(3));
        assertTrue(DivThreeEfficiently.isMultipleOfThree(6));
    }


    @Test
    public void testOddNegative() {
        assertFalse(DivThreeEfficiently.isMultipleOfThree(-1));
        assertFalse(DivThreeEfficiently.isMultipleOfThree(-4));
        assertFalse(DivThreeEfficiently.isMultipleOfThree(-11));
    }

    @Test
    public void testOddPositive() {
        assertFalse(DivThreeEfficiently.isMultipleOfThree(1));
        assertFalse(DivThreeEfficiently.isMultipleOfThree(4));
        assertFalse(DivThreeEfficiently.isMultipleOfThree(11));
    }
}

Answer 1

Computers aren't humans. A human might find it easiest to apply a divisibility rule. A computer, though, doesn't care.

The simplest code would be to check n % 3 == 0. The modulo operator uses the JVM opcode irem, which is about as efficient as you can get.

On an Intel CPU, irem is probably implemented using the IDIV (signed divide) instruction. On most modern x86-compatible processors, IDIV with a 32-bit operand uses 10 to 30 micro-operations and has a latency of 20 to 61 clock cycles. More importantly, the trend on newer and more powerful hardware is for IDIV to take fewer clock cycles. In other words, writing the program as if it were a RISC processor is a counterproductive "optimization" — it would be better to let the hardware perform the division operation to its full potential.

For comparison…

javap -c DivThreeEfficiently

public final class DivThreeEfficiently {
  public static boolean isMultipleOfThree(int);
    Code:
       0: iload_0       
       1: ifge          7
       4: iload_0       
       5: ineg          
       6: istore_0      
       7: iconst_0      
       8: istore_1      
       9: iconst_0      
      10: istore_2      
      11: iload_0       
      12: ifeq          46
      15: iload_0       
      16: iconst_1      
      17: iand          
      18: iconst_1      
      19: if_icmpne     25
      22: iinc          2, 1
      25: iload_0       
      26: iconst_1      
      27: ishr          
      28: istore_0      
      29: iload_0       
      30: iconst_1      
      31: iand          
      32: iconst_1      
      33: if_icmpne     39
      36: iinc          1, 1
      39: iload_0       
      40: iconst_1      
      41: ishr          
      42: istore_0      
      43: goto          11
      46: iload_1       
      47: iload_2       
      48: if_icmpne     55
      51: iconst_1      
      52: goto          56
      55: iconst_0      
      56: ireturn       
}

Div3MoreEfficiently.java

public class Div3MoreEfficiently {
    private Div3MoreEfficiently() {}

    public static boolean isMultipleOfThree(int n) {
        return n % 3 == 0;
    }
}

javap -c Div3MoreEfficiently

public class Div3MoreEfficiently {
  public static boolean isMultipleOfThree(int);
    Code:
       0: iload_0       
       1: iconst_3      
       2: irem          
       3: ifne          10
       6: iconst_1      
       7: goto          11
      10: iconst_0      
      11: ireturn       
}

Answer 2

Division instructions are often slow, because they have to do a conditional subtract once for each bit of the quotient. It's possible to write code which may perform better than this, but a loop which requires an iteration for each bit of the quotient isn't apt to do so.

I would suggest that if a number is positive, you may start by adding the upper 11 bits to the middle 10 and lower 10. That will yield a 12-bit value which will be a multiple of 3 if and only if the original value was (call that value Q). Multiply Q by 0x5556 and shift right by 16, multiply by 3, and subtract from Q. That result will be zero if and only if the original number was a multiple of three. For processors with a single-cycle multiply but a 32-cycle divide, this approach may end up being noticeably faster than using a divide instruction. Something like

int Q = (n >> 20) + ((n >> 10) & 0x3FF) + (n & 0x3FF);
Q -= ((Q*0x5556) >> 16)*3; // Divide Q by three and then multiply by 3 to get remainder
// Q will be zero if and only if the original number was a multiple of three

An alternative approach that might be faster on some processors would be:

if (n<0) n=-n;
int q = (int)((n*0x55555556L) >> 32);
n=n-q-q-q;    
return n==0;

Whether that one performs well would depend upon whether the JITter recognizes that both arguments to the long multiply are actually int.

Answer 3

I guess, a really fast solution on a modern CPU looks like this:

int mask = 0x2AAAAAAA; // special handling for the sign bit
int diff = 2 * Integer.bitCount(x & mask) + Integer.bitCount(x & ~mask);

Don't be fooled by the complicated code behind it, it's an intristic and translates to a single cycle instruction.

Now we have a number between 0 and 48, which is divisible by 3 iff x is divisible by 3. The fastest way is probably a table packed into a single long.

 return (TABLE << diff) < 0;

EDIT

I've change the above code slightly to make the explanation simpler.

The remainder modulo 3 is the same for 1 and 10, as 10 % 3 = 1, which means that in decimal the position of a digit doesn't matter for this remainder. This leads to the well-known digit sum rule.

In binary, it doesn't work exactly like this as 2 % 3 != 1. But 4 % 3 = 1, so we can rewrite (8*a + 4*b + 2*c + d) % 3 = (2*(a+c) + (b+d)) % 3. Since every digit is either zero or one, all we need is to count the ones in the appropriate positions. As the weight of the highest bit is -2**31, it needs a special handling (see the mask).

EDIT

I see I missed a trivial optimization. This is the whole code afterwards:

private static final long TABLE = 0x9249249249240000L;

int diff = Integer.bitCount(x & 0x2AAAAAAA) + Integer.bitCount(x);
return (TABLE << diff) < 0;

EDIT

Fixed (long TABLE is needed) and tested exhaustively for all ints.

BENCHMARK

My benchmark produces very different results. As benchmarking Java is pretty hard, I'd trust my results using caliper more. It's sad, but the winner is supercat, not me.

I guess, I have to tune the benchmark a bit, as finding anything to tune in my two lines is rather impossible.

PROBABLE WINNER

I guess, this late answer by James_pic using some math could be the fastest.

Answer 4

Given how fast it should be I'd tend toward advocating a brute-force test, something like:

for (int i=-100000; i<100000; i++)
    assertEquals(DivThreeEfficiently.isMultipleOfThree(i), i%3==0);

This makes the intent more apparent, reduces the amount of code, and still covers a lot more cases than the test code you used. It would probably still be good to cover a few of the obvious corner/limit cases (e.g., minimum/maximum values), but this seems to simplify the "sunny day" testing while expanding coverage substantially.

Answer 5

As your original implementation doesn't produce the correct results for 21, 42, 69, 81, 84, 87, and 93 (that's just from 0 to 100 !), I wanted to provide a more "common" way to handle the question of divisibility by three. This is what many humans do when they are faced with a number with a lot of digits and want to determine if it's divisible by three or not:

A number is divisible by 3 if the sum of all its digits is divisible by three

The main benefit of this approach is that it's easier to understand for the human mind. This can be turned into a nice little recursive method:

public static boolean isDivisibleByThree(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 isDivisibleByThree(sum);
}

Admittedly, this is not as fast as your current approach (according to my benchmarking, it's about twice as slow), but it does produce the correct results. (Even for the extreme value of Integer.MIN_VALUE).

Although in the end, nothing is as readable for a programmer as i % 3 == 0

Answer 6

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.

Answer 7

In the spirit of premature optimisation, here's a fast method based on modular arithmetic:

import java.math.BigInteger;

private static final int MULTIPLIER =
  BigInteger.valueOf(3).modInverse(BigInteger.valueOf(2).pow(32)).intValue();
private static final int LOWER_LIMIT = Integer.MIN_VALUE / 3;
private static final int UPPER_LIMIT = Integer.MAX_VALUE / 3;

public static boolean divideFast(int i) {
  int j = i * MULTIPLIER;
  return LOWER_LIMIT <= j && j <= UPPER_LIMIT;
}

The idea is that in Java, multiplication is modulo 2³² (since it wraps on overflow), and in modular arithmetic you can divide by multiplying - which is generally faster than dividing. Every odd number has a "reciprocal" - a number that you can multiply it by to give 1 - since odd numbers are coprime to 2³². The reciprocal of 3 is MULTIPLIER.

If i is divisible by 3 in regular integer arithmetic, then i * MULTIPLIER will be i / 3. If i is not divisible by 3, then it's still true that 3 * (i * MULTIPLIER) === i modulo 2³², but only because multiplication wraps on overflow.

So, the numbers that are divisible by 3 are precisely the numbers where we can multiply i * MULTIPLIER by 3 without overflow. I.e, the numbers where i * MULTIPLIER is between Integer.MIN_VALUE / 3 and INTEGER.MAX_VALUE / 3.

In my benchmark, this method works out at 0.72ns per check, versus 0.93ns per op for the next closest, @maaartinus.

Answer 8

Did you make sure that the division is your bottleneck? In most cases a smart compiler/JITer will optimize that to a multiplication and won't take much cycles of your program.

In case that really slows your program down, you can use the solution here. It uses the fact that if the sum of all digits of a number in base N divides a divisor M of N-1 then that number is divisible by M. The original version deals with unsigned numbers so we need a little change

private static int reduce(int i) {
    if (i >= 6)
        return reduce((i >> 2) + (i & 0x03));
    else
        return i; // Done.
}

public static boolean isMultipleOfThree(int i) {
    if (i < 0) i = -i;
    // Sum of digits in base 4
    i = (i >> 16) + (i & 0xFFFF);
    i = (i >> 8) + (i & 0xFF);
    i = (i >> 4) + (i & 0xF);
    i = reduce(i);
    return i == 0 || i == 3;
}

You can also do it in base 16 but it'll take more comparisons and maybe not faster than this version.