[Math] Bit representation and divisibility by 3

binarybit-stringsdivisibility

I was reading about how to know if a number is divisible by 3 given binary representation of the number.

After googling a bit I read a statement and I am puzzled how is this correct.

we have to just count the number of 1's (set bits) at even position and number of 1's (set bits) at the odd positions. If the difference is divisible by 3, the number is divisible by 3.

Can anyone please help in understanding the logic behind this.

Best Answer

If we start counting from $0$ the bits in even position are worth $1,4,16,\ldots 2^{2k}$. When you divide any of these by $3$ you leave a remainder $1$. The bits in odd position are worth $2,8,32,\ldots 2^{2k+1}$. When you divide any of these by $3$ you leave a remainder of $2$ or, equivalently, $-1$. The remainder of dividing by $3$ is then the number of bits in even position minus the number of bits in odd position.