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.

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.