Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Efficient way to check if a number is multiple of three. 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));
    }
}
share|improve this question
56  
I suppose n % 3 == 0 is cheating? –  Simon André Forsberg Jun 2 at 21:50
5  
As stated below, needs more tests. isMultipleOfThree(21) returns false. –  Origineil Jun 2 at 22:27
3  
The next test will be to confirm that your approach actually is a performance gain, which is far from obvious... –  assylias Jun 2 at 22:28
18  
@user3580294 This is a perfect demonstration of the dangers of early CPU/memory resource optimization: how many hours of engineer time has been spent on this one question (however interesting) which has most likely been contemplated by others many times over the years? "Congratulations! You've saved us up to 47¢ every month over the next ten years—and all for well under $18,271 to build!" :) –  David Harkness Jun 3 at 5:24
4  
Yes, as someone said, it's true that division is a slow instruction. But I strongly suspect that (n % 3) == 0 would still execute much, much faster than a more complex function that includes loops and multiple variables. In practice, anytime I have a problem like this I do the "%". If I had an environment where I had to do such an operation thousands of times per second on a very limited CPU, I'd try different options and do timing tests. But I'd be surprised if there's a faster way than n % 3. –  Jay Jun 3 at 20:39

8 Answers 8

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       
}
share|improve this answer
5  
On most processors, getting a remainder uses a division operation. If this approach worked correctly (I'm not sure it does) it's just barely possible that it could end up a little faster than using division. That would probably depend on the underlying processor though. –  Jerry Coffin Jun 2 at 22:26
3  
@JerryCoffin 1) If n % 3 == 0 is not the most obviously correct implementation, then I don't know what will convince you. 2) I've added more justification about clock efficiency. Also see benchmarks. –  200_success Jun 3 at 18:54
2  
By "this approach", I meant the OP's approach, not the i%3==0 (which I agree is pretty obviously correct--which is why I used it to create the "gold" value in my answer). As to clock efficiency: not saying his approach is more efficient, just that I can imagine there being at least one processor on which it could be. –  Jerry Coffin Jun 3 at 18:59
    
It's true that the best way to write this in Java is to just use i % 3 == 0, but certainly not because an idiv instruction is particularly efficient. It's horribly inefficient (we can do with a multiplication and a shift) as a matter of fact and we can do much better, but a good compiler will do this for you. gcc certainly does, but I'm not sure if HotSpot does the same. –  Voo Jun 5 at 18:48

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.

share|improve this answer
    
0x5555 or 0x5556? –  ErikE Jun 3 at 0:49
1  
@ErikE: 0x5556. For integers 1-65535, (n*0x5555 >> 16) will compute (n-1)/3. Using 0x5556 avoids the -1 term. –  supercat Jun 3 at 4:44
    
The second code snippet is kind of like what gcc does with i % 3 in C++. I don't know how good JITs generally are with arithmetic, but I'd be somewhat disappointed if my JIT doesn't know this trick for constant divisors and use it where appropriate, so that I don't have to :-) –  Steve Jessop Jun 5 at 9:18

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.

share|improve this answer
    
Some explanation of why this works would be in order. (Ie. why the digit sum test for divisibility by 3 in binary is the same as for 11 in decimal). And also why the offset of 1 in two complements means that treating the sign bit as an even indexed bit yields the correct result. Finaly your return statement seems to return true if any diff higher than the current divides 3 - I think you need to catch only the least bit. –  Taemyr Jun 3 at 7:22
    
@Taemyr I'm not getting your last sentence. The left shift shifts the relevant bit into the 31st position so I can test the sign. –  maaartinus Jun 3 at 15:36
1  
That TABLE looks like one of the few places where octal notation might actually be useful. I think octal notation should have used something like 0q rather than a naked leading 0, but 01111111111111111111111L is a cute constant, isn't it? –  supercat Jun 3 at 18:15
    
@supercat I guess so. But I hate octal, the current notation is totally brain damaged (I'd propose the 0o prefix). I must confess that I generated the constant (by trying a few multiples of 3) and never looked at the value. But logically, every third bit is set. –  maaartinus Jun 3 at 19:26
    
@maaartinus After you have shiftet the relevant bit into the 31st position how you know that all the other bits are 0? –  Taemyr Jun 4 at 6:21

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. Unless you do C/C++, in which case I believe that'd be (i % 3) == 0

share|improve this answer
5  
Some C and/or C++ programmers might use (i%3)==0 but it's not necessary--% has higher precedence than ==, so it means the same thing with or without parentheses. –  Jerry Coffin Jun 2 at 23:52
2  
Rather than looking at the number in base 10, looking at it in base 16 would be more efficient. –  supercat Jun 2 at 23:57
    
@JerryCoffin Thanks, I thought those operators had a different precedence between Java and C, but I think I might have confused it with && and ==. –  Simon André Forsberg Jun 3 at 0:05
    
@SimonAndréForsberg: Perhaps--or, perhaps, bitwise and -- for example, if somebody writes if (x&1 == 1), they probably intend if ((x&1)==1), where the original means the same as: if (x & (1==1)). –  Jerry Coffin Jun 3 at 0:09
1  
Repeatedly divide by 10 is very slow. In base 4 and base 16 the statement "A number is divisible by 3 if the sum of all its digits is divisible by three" also applies, and it's much easier to sum the digits in those bases. Please see my answer –  Lưu Vĩnh Phúc Jun 5 at 14:14

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.

share|improve this answer
    
"sunny day" testing? –  Simon André Forsberg Jun 2 at 22:17
7  
@SimonAndréForsberg: "sunny day" is just testing the basic functionality, without going to any effort to find boundary cases and such that are particularly likely to break the unit under test. –  Jerry Coffin Jun 2 at 22:22

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.

share|improve this answer
1  
You're basically measuring the memory and virtual dispatch overheads. See my update. –  maaartinus Jun 3 at 19:53
    
@maaartinus In Rev 3, I have removed the array allocation from the timings, cuting ~ 30 ms across the board without significantly changing the relative ranking of the solutions. I'd consider the solutions from you and supercat to have the same performance. (I couldn't get Caliper to run — their API is unstable, the examples on the website don't work against their published caliper-1.0-beta-1-all.jar, and neither does your DivisibilityBenchmark. Not your fault that the project is a mess.) I don't see any reason to distrust my results, though I can understand if they differ by CPU type. –  200_success Jun 3 at 21:12
1  
@200_success With your benchmark, the first solution saves quite some time, because when it runs, the call site is monomorphic. You'd need to start a new JVM, which Caliper does. Their API is pretty stable since over one year, the problem is that their docs are even much more stable (read obsolete), or something like this. I'm using the version from git. If you like maven, try JMH. –  maaartinus Jun 4 at 0:26
1  
You shouldn't trust any benchmark, unless it doesn't matter. Note that you're reporting "supercat Rev 4" to be more than twice slower than yours and Caliper reports it to be faster. I'm not saying, you have to do anything, just for the record: Microbenchmarking is hard, especially in Java. –  maaartinus Jun 4 at 0:35
    
@maaartinus Rev 4 confirms your observation that the benchmark gave an unfair advantage to the first few test cases. Thank you for enlightening me. I've learned something new about JIT behaviour and benchmarking. I'd like to award you a bounty, but first I have to wait until the close vote on this question expires. –  200_success Jun 4 at 5:22

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 232 (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 232. 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 232, 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.

share|improve this answer

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.

share|improve this answer

protected by rolfl Jun 3 at 0:29

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.