Check if a number is divisible by 3

Question

I need to find whether a number is divisible by 3 without using %, / or *. The hint given was to use atoi() function. Any idea how to do it?

Answer 1

The current answers all focus on decimal digits, when applying the "add all digits and see if that divides by 3". That trick actually works in hex as well; e.g. 0x12 can be divided by 3 because 0x1 + 0x2 = 0x3. And "converting" to hex is a lot easier than converting to decimal.

Pseudo-code:

int reduce(int i) {   if (i > 0x10)     return reduce((i >> 4) + (i & 0x0F)); // Reduces 0x102 to 0x12 to 0x3.   else    return i; // Done. } bool isDiv3(int i) {   i = reduce(i);   return i==0 || i==3 || i==6 || i==9 || i==0xC || i == 0xF; } 

[edit] Inspired by R, a faster version (O log log N):

int reduce(unsigned i) {   if (i >= 6)     return reduce((i >> 2) + (i & 0x03));   else    return i; // Done. } bool isDiv3(unsigned  i) {   // Do a few big shifts first before recursing.   i = (i >> 16) + (i & 0xFFFF);   i = (i >> 8) + (i & 0xFF);   i = (i >> 4) + (i & 0xF);   // Because of additive overflow, it's possible that i > 0x10 here. No big deal.   i = reduce(i);   return i==0 || i==3; }