Efficiently checking if a number is divisible by 3 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 &lt; 0) n = -n;

        int evenCtr = 0;
        int oddCtr = 0;

        while (n != 0) {
            if ((n &amp; 1) == 1) { 
                oddCtr++;
            } 
            n = n&gt;&gt;1;
            if ((n &amp; 1) == 1) {
                evenCtr++;
            } 
            n = n&gt;&gt;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));
    }
}
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       
}