27

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.

3

3 Answers 3

65

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.

6
  • Thanks alot, Do you know what is the mathematical explanation for this trick?
    – Itay Braha
    Commented Sep 8, 2016 at 9:00
  • 3
    @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.
    – Andreas H.
    Commented Sep 8, 2016 at 9:10
  • Divisibility test for 11 in decimal is same as that of 3 in binary. Also, 3 in binary is 11. Am I missing something ? Commented Jan 5, 2018 at 16:28
  • 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)
    – Rogue
    Commented Apr 23, 2018 at 16:09
  • 1
    here's the mathematical proof Determine whether or not a binary number is divisible by $3$
    – phuclv
    Commented Feb 17, 2019 at 4:42
1

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

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).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.