In middle school you probably learned a simple "trick" to check whether a number is divisible by 3. Sum up the digits (recursively, if needed) and the original number is divisible by 3 if the computed sum is divisible by 3. Here is a twist: what if you only had access to the binary representation of the number? This could be the case in a hardware based implementation or a low-complexity firmware based implementation. Or maybe we want to answer the question just for fun. Either way, we'll derive a simple rule here to check divisibility of a binary number by 3.

Any binary number

$$x$$ can be written as  $$x = \sum_{n=0}^{N-1} b_n 2^n$$ , where $$b_n \in {0, 1}$$ are the bits that make up the binary representation.

For example,

$$x=13$$ can be decomposed as $$x = 8 + 4 + 1 = 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0$$ , implying the bits representing $$x$$ are $$b_0=1,b_1=0,b_2=1,b_3=1$$ . 

Let's recall the binomial theorem, which says that the polynomial

$$(x+y)^n$$ can be expanded as follows:

$$(x+y)^n = \sum_{k=0}^n {n \choose k}x^k y^{n-k}$$ .

Setting

$$x=3$$ and $$y=-1$$ in the theorem, we get:

$$2^n = \sum_{m=0}^n {n \choose m} 3^m (-1)^{n-m}$$

$$= {n \choose 0} 3^0 (-1)^n +  \sum_{m=1}^n {n \choose m} 3^m (-1)^{n-m}$$

Now, let's plug this representation of

$$2^n$$ back into the binary expansion of $$x$$ to get:

$$x = \sum_{n=0}^{N-1} b_n 2^n$$

$$= \sum_{n=0}^{N-1} b_n \left[  (-1)^n + 3d(n) \right]$$

$$= \underbrace{\sum_{n=0}^{N-1}(-1)^n b_n}_{\Delta} + \underbrace{3 \sum_{n=0}^{N-1} b_n d(n)}_{\text{Multiple of 3}}$$ .

Now we are in business, because we have written

$$x$$ as a sum of two terms: one which is a multiple of 3 and another term $$\Delta$$ , which is a linear combinations of the bits of $$x$$ . For $$x$$ to be a multiple of 3, the linear combination has to be a multiple of 3, i.e.

$$x$$ is divisible by 3 if and only if $$\Delta$$  is divisible by 3. 

This linear combination can be written as

$$b_0-b_1+b_2-...$$ , i.e. add up the non-zero bits in the even numbered spots (counting from the right, or the least significant bit) with a positive sign and the non-zero bits in the odd numbered spots  with a negative sign. In other words, find the difference in the number of non-zero bits in the even locations and number of non-zero bits in the odd locations. This difference must be divisible by 3. If $$\Delta=0$$ or $$\Delta=3, x$$ is divisible by 3. If $$\Delta=1$$ or $$\Delta=2, x$$ is not divisible by 3. If $$\Delta>3$$ , the method can be applied recursively by setting $$x=\Delta$$ . 

Let's work through an example,

$$x=75$$ , which has the binary representation 1001011. The bits in the even locations are shown in red and they sum up to 2. The bits in the odd locations are shown in green and they also sum  up to 2. In this case, $$\Delta=0$$ , implying $$x=75$$ is divisible by 3.