Divisibilty by 3

How to check whether a number is divisible by 3 or not without using +,*,-,/,% operators?

If you can use bit operators ( >>, & ), than you can use the property of mod operation

A*B mod 3 = ( (A mod 3) * (B mod 3) ) mod 3

than

1010 = 10102

10 = 23 + 21 = 21 * (22 + 1) = 2 * (2 * 2 + 1)

10 3 = ( 2 3 * ( ( 2 3 * 2 3 ) 3 + 1 3 ) 3 ) 3

The only problem here is +1 operation, but you can use state machine to compute mod3

last bit
0 1
actual mod 0 0 (2*act. mod+0) 1 (2*act. mod+1)
1 2 (2*act. mod+0) 0 (2*act. mod+1)
2 1 (2*act. mod+0) 2 (2*act. mod+1)

I’m not sure if that was clear so I’m adding code in Java:

private static boolean mod3( int n ) {
    int mod = 0;
    while ( n > 0 ) {
        final int bit = n & 1;
        if ( bit == 0 ) {
            switch ( mod ) {
            case 0:
                mod = 0; // 2*0;
                break;
            case 1:
                mod = 2; // 2*1;
                break;
            case 2:
                mod = 1; // (2*2) % 3;
                break;
            }
        } else {
            switch ( mod ) {
            case 0:
                mod = 1; // 2*0 + 1
                break;
            case 1:
                mod = 0; // (2*1 + 1) % 3
                break;
            case 2:
                mod = 2; // (2*2 + 1) % 3
                break;
            }
        }
        n >>= 1;
    }
    return mod == 0;
}
1 Like