title: Check division by 3 with binary operations?
body: <p>I've read <em><a href="https://stackoverflow.com/a/6647785/859154">this interesting answer</a></em> about  "<em>Checking if a number is divisible by 3</em>"</p>
  
  <p>Although the answer is in Java , it seems to work with other languages also.</p>
  
  <p>Obviously we can do : </p>
  
  <pre><code>boolean canBeDevidedBy3 = (i % 3) == 0;
  </code></pre>
  
  <p>But the interesting part was this other calculation : </p>
  
  <pre><code>boolean canBeDevidedBy3 = ((int) (i * 0x55555556L &gt;&gt; 30) &amp; 3) == 0;
  </code></pre>
  
  <p>For simplicity : </p>
  
  <p><code>0x55555556L = "1010101010101010101010101010110"</code>  </p>
  
  <p>Nb</p>
  
  <p>There's also another method to check it : </p>
  
  <blockquote>
    <p>One can determine if an integer is divisible by 3 by counting the 1
    bits at odd bit positions, multiply this number by 2, add the number
    of 1-bits at even bit positions add them to the result and check if
    the result is divisible by 3</p>
  </blockquote>
  
  <p>For example : </p>
  
  <p>93<sub>10</sub> ( is divisible by 3)<br>
  01011101<sub>2</sub></p>
  
  <p>It has <code>2</code> bits in the odd places and <code>4</code> bits at the even places ( place is the zero based of the base <code>2</code> digit location)</p>
  
  <p>So <code>2*1 + 4 = 6</code> which is divisible by <code>3</code>.</p>
  
  <p>At first I thought those 2 methods are related but I didn't find how.</p>
  
  <p><strong>Question</strong></p>
  
  <p>How does </p>
  
  <pre><code>  boolean canBeDevidedBy3 = ((int) (i * 0x55555556L &gt;&gt; 30) &amp; 3) == 0;
  </code></pre>
  
  <p>— actually determines if <code>i%3==0</code> ?</p>