Algorithms computing if a number is a multiple of 3

Problem Detail: 

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.

Asked By : Stephane Rolland

Answered By : mhum

Consider the following two observations (left as an exercise to the reader):

1. The even powers of two are 1 modulo 3.
2. The odd powers of two are -1 modulo 3.

We conclude that that a number (in binary) is divisible by three if and only if the sum of the bits in the even positions equals the sum of the bits in the odd positions modulo 3.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7879