Oops, my mistake, this is clearly O(n) where n is the number of bits, so O(log(v)) where v is the value. Here's a Python implementation (which has bignums): def div3_check(n): v = n while v > 3: s = 0 while v != 0: s += v & 0x3 v >>= 2 v = s return v in (0, 3) You can also replace the multiple passes with a single pass, by renormalizing the sum on the fly (keeping it in the range 0..3): def div3_check(n): v = n s = 0 while v != 0: s += v & 0x3 s = (s >> 2) + (s & 0x3) v >>= 2 return s in (0, 3) Tom Tom Karzes writes:
The same trick that works in base 10 also works in base 4. So just group the bits into pairs and add them, then repeat on the result until the sum is less than 4. If the sum is divisible by 3 (i.e., if the sum is 3 (or 0, if the original number was 0)), then the number is divisible by 3. Otherwise it isn't.
Example:
101110001 (369) -> 1 + 01 + 11 + 00 + 01 = 110 (6) -> 110 (6) -> 1 + 10 = 11 (3)
Answer: yes
I think this is an n*log(n) algorithm where n is the number of bits, so log(v)*log(log(v)) where v is the value.
Tom