CareerCup

initialize sum=0;
for the first and second bit check if they are set and add 1 to sum if first bits is set and add 2 to sum if second bit is set. then proceed on remaining stream from 3rd bit onwards.for every odd bit set add 1 to sum and for evry even bit set substract 1 from sum and meanwhile also make it sure that when sum exceeds 3 den set sum as sum%3.thus at any point of time the value of sum would tell u the divisibily.if sum=0,3 then its divisible else not..

if the number of 1's in odd position = number of 1's in even position, number is divisible by 3

Using the property(if the number of 1's in odd position = number of 1's in even position, number is divisible by 3) above, maintain 2 counters to count the number of 1s occuring in odd and even positions of the digit. At any point of time, if the counters are equal that number is divisible by 3.

Check for 21 -> 10101

How about
N is divisible by 3 if and only if
# of 1's in even position == # of 1's in odd position (mod 3).

In case of 21: 0 == 3 (mod 3)

In fact, using induction you can prove the following:

Given a non-negative number n, let odd(n) be the count of 1's in the odd positions of n's binary representation and even(n) is the count of 1's in even position. Then

odd(n) - even(n) = n (mod 3)

Or, in other words, (odd(n) - even(n)) % 3 == n % 3.