# 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