title: Divide a signed integer by a power of 2
body: <p>I'm working on a way to divide a signed integer by a power of 2 using only binary operators (&lt;&lt; >> + ^ ~ &amp; | !), and the result has to be round toward 0. I came across <a href="https://stackoverflow.com/questions/5061093/dividing-by-power-of-2-using-bit-shifting">this question</a> also on Stackoverflow on the problem, however, I cannot understand why it works. Here's the solution:</p>
  
  <pre><code>int divideByPowerOf2(int x, int n)
  {
      return (x + ((x &gt;&gt; 31) &amp; ((1 &lt;&lt; n) + ~0))) &gt;&gt; n;
  }
  </code></pre>
  
  <p>I understand the <code>x &gt;&gt; 31</code> part (only add the next part if <code>x</code> is negative, because if it's positive <code>x</code> will be automatically round toward 0). But what's bothering me is the <code>(1 &lt;&lt; n) + ~0</code> part. How can it work?</p>