Stream is divisible by 3 or not

Suppose you are getting an infinite binary stream of characters then after any point of time you need to print whether the no is divisible by 3 or not, how will you do that?


Method:

A binary number is divisible my 3 if the number of ‘1s’ at even position – number of ‘1s’ at odd positions in the binary digit is divisible by 3

498 in binary is 111110010 no of even ‘1’ bits =3 and no of odd ‘1’ bits =3 so 3-3 =0 Hence 498 is divisible by 3.

So in the infinite stream of binary characters maintain two counters odd and even and update them whenever you get a ‘1’ at the position. Whenever you need to check the divisibility by 3 subtract odd from even and check the divisibility of the remainder from 3.

This question can be generalized for checking divisibility by other numbers as well. It is easy in the case of even numbers such as

If the rightmost bit is 0, then it is divisible by 2,
If rightmost two bits are zeros then the number is divisible by 4,
If rightmost three bits are zeros the number is divisible by 8 and so on.

However it is tricky in case of odd numbers. We just saw for 3, let us check for 5 as well

For 5, note that 2^j == 1, 2, -1, -2 mod 5 for j == 0, 1, 2, 3 mod 4 respectively.

So let A, B, C, D be the number of bits which are 1 with n congruent to 0, 1, 2, 3 mod 4,
and take A + 2 B - C - 2 D. Then x is divisible by 5 iff the result is divisible by 5.

E.g. for 11110101 we have A = 2, B = 1, C = 2, D = 1, result = 0 so it's divisible by 5.
You may find it easier to start at the right end and go digit-by-digit, adding or subtracting 1 or 2 for each 1 as appropri