Algorithms computing if a number is a multiple of 3 When doing mental calculus one can do:


Given an integer k, sum all the digits (in base 10),
and if the result is a multiple of 3, then k is a multiple of 3.


Do you know of any algorithm working similarily but operating on binary numbers digits (bits)? 


At first, I was thinking of using the ready made functions of my
language converting integer to ascii to perform the convertion from
base 2 to base 10, then apply the mental calculus trick. But of
course then I could also encode the base convertion 2 to 10 myself.
I have not done it yet, but I'll give it a try.
Then I have thought of euclidian division in base 2...


However I wonder if there are other means, algorithms.
What about a finite state automaton for the job?



Of course the magic is just computation modulo 3. Adding symbol $a$ behind string $x$ means the "binary value" of the string goes from $val(x)$ for $x$ to $2\cdot val(x)+a$ for $xa$. Consequently from state $p$ and symbol $a$ we move to state $2p+a \bmod 3$, for $p\in \{0,1,2\}$ and $a\in \{0,1\}$. Note $x\in \{0,1\}^*$ is a string, wheras $val(x)\in \Bbb{N}$ is its value as binary string.