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.

Solution 1

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.

Solution 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

Comments

[Admin]

This question is perhaps better suited for math.SE.

[G. Bach]

Solution on CS.SE. Similar solutions work for any n-ary number system and divisor.

[phuclv]

Check if a number is divisible by 3

[Itay Braha]

Thanks alot, Do you know what is the mathematical explanation for this trick?

[Andreas H.]

@ItayBraha: Not a full explanation: This is the same trick as for testing if a decimal number is divisible by 11. The keyword here is the alternating digit sum. If and only if the alternating digit sum in decimal radix is divisible by 11, so is the original number. It can be used when the number you want to test divisibility for is one more than the radix of the number system. TO test for divisibility of numbers one below the radix (e.g. 9 for the decimal system) use the ordinary digit sum. So one can also easily test divisibility by 17 in hexadecimal representation.

[Ashok Bijoy Debnath]

Divisibility test for 11 in decimal is same as that of 3 in binary. Also, 3 in binary is 11. Am I missing something ?

[Rogue]

if you really wanna get profound, it means you can add all the digits together in a binary number to determine that it was already divisible by 1 (divisibility of n-1 rule)

[phuclv]

here's the mathematical proof Determine whether or not a binary number is divisible by $3$