How to know if a binary number divides by 3?

Question

I want to know is there any divisible rule in binary system for dividing by 3.

For example: in decimal, if the digits sum is divided by 3 then the number is devided by 3. For exmaple: 15 -> 1+5 = 6 -> 6 is divided by 3 so 15 is divided by 3.

The important thing to understand is that im not looking for a CODE that will do so.. bool flag = (i%3==0); is'nt the answer I'm looking for. I look for somthing which is easy for human to do just as the decimal law.

Answer 1

There is a way quite similar to the checksum for decimal numbers: but you have to crossout doubles (two 0's or two 1's after each other) in advance, until you end up with something of the form <1|0>0101010... Then count the 1's: if their sum (=checksum) is divisible by three, so is the original number.

Example:

10111001 -> 101001 ->1011 -> 10 : yields checksum 1 -> not divisible
10111010 -> 101010 : yields checksum 3 -> is divisible  
10111011 -> 101011 -> 1010 : yields checksum 2 -> not divisible

Maybe the easiest way to see the reason why this works would be to set up a DFA (deterministic finite automata) with three states to check for divisibility by three (see eg. Chris Staekers videos on theory of computation, Episode 5, DFA's formally).

Answer 2

i would like to divide the bits into many small pieces from right to the left ,each piece has 2 bits and if the sum of them is divisible by 3 then the number is divisible by 3. for example,we have 100111(39),we divide this number into 3 piece from right to left then we have 11,01 and 10.The sum of them is 110 which is divisible by 3 then the number 100111 is divisible by 3. example 2 : 1011010 divide them into pieces so now we have 10,10,01,01.the sum of them is 110 which is divisible by 3 then the 1011010 is divible by 3. Also note that this trick is still right for 7 but each piece must have 3 bits instead of 2

Answer 3

Refer to this website: How to Tell if a Binary Number is Divisible by Three

Basically count the number of non-zero odd positions bits and non-zero even position bits from the right. If their difference is divisible by 3, then the number is divisible by 3.

For example:

15 = 1111 which has 2 odd and 2 even non-zero bits. The difference is 0. Thus 15 is divisible by 3.

185 = 10111001 which has 2 odd non-zero bits and 3 even non-zero bits. The difference is 1. Thus 185 is not divisible by 3.

Explanation

Consider the 2^n values. We know that 2^0 = 1 is congruent 1 mod 3. Thus 2^1 = 2 is congurent 2*1 = 2 mod 3. Continuing the pattern, we notice that for 2^n where n is odd, 2^n is congruent 1 mod 3 and for even it is congruent 2 mod 3 which is -1 mod 3. Thus 10111001 is congruent 1*1 + 0*-1 + 1*1 + 1*-1 + 1*1 + 0*-1 + 0*1 + 1*-1 mod 3 which is congruent 1 mod 3. Thus 185 is not divisible by 3.