How to Tell if a Binary Number is Divisible by Three

Answer:
If the number of even bits minus the number of odd bits is a multiple of 3 (e.g. -3,0,3,6, etc) then the number is divisible by three.

Example:
498 is evenly divisible by 3. 498 in binary is 111110010.
Counting from the right there are 3 even bits and 3 odd bits.

This was a question from my neural networks class and I couldn’t find any help on the internet. I hope I’m not spoiling anyone’s homework by writing it here.

Posted by Greg Pinero (Primary Searcher) on Apr 3rd, 2006 and is filed under Idle Curiosities, Machine Learning, Other.

Both comments and pings are currently closed.

Add this post to Del.icio.us - Digg

2 Responses to “How to Tell if a Binary Number is Divisible by Three”

  1. Doug Preston says:
    November 7th, 2007 at 4:32 pm

    Would someone please confirm the following?

    Interesting to note that (2^m -1) can be tested for divisibility by three using the above result, for positive integers m > 0.

    If m is even, then (2^m -1) is represented in binary as an even-length string of ones.
    Therefore, even-bits minus odd-bits is zero, which is divisible by three.

    If m is odd, then (2^m -1) is represented in binary as an odd-length string of ones.
    Therefore, even-bits minus odd-bits is negative one, which is not divisible by three.

    So…
    For all even positive integers m > 0:
    (2^m -1) is divisible by three.

    For all odd positive integers m > 0:
    (2^m -1) is not divisible by three.

  2. Greg Pinero (Primary Searcher) says:
    November 7th, 2007 at 4:39 pm

    That sounds like it might work Doug. Interesting observation.