binary divisibility by 3 [duplicate]

This question already has answers here: Closed 12 years ago.

Possible Duplicate:

Check if a nu开发者_Python百科mber is divisible by 3

Is it true that a binary number is divisible by 3 iff it has an even number of ones? like 11000 is divisible by 3 whereas 1110 is not.

---

No - there is a trick but it's a little more complicated than that - you have to count the number of 1s at even positions and the number of 1s at odd positions. See e.g. Check if a number is divisible by 3.

---

No, that's wrong. For example 5_dec = 101_bin is not divisble by 3. To check for divisbility by three, you have to count the number of ones in even position and substract the number of ones in odd positions. If the difference is divisble by three, the original number is divisbilble by three (which, in turn, can be checked by reiterating the same rule).