title: How can I strength reduce division by 2^n + 1?
body: <p>I need to perform some integer divisions in the hot path of my code. I've already determined via profiling and cycle counting that the integer divisions are costing me. I'm hoping there's something I can do to strength reduce the divisions into something cheaper.</p>
  
  <p>In this path, I am dividing by 2^n+1, where n is variable. Essentially I want to optimize this function to remove the division operator:</p>
  
  <pre><code>unsigned long compute(unsigned long a, unsigned int n)
  {
      return a / ((1 &lt;&lt; n) + 1);
  }
  </code></pre>
  
  <p>If I were dividing by 2^n, I would just replace the div with a shift-right by n. If I were dividing by a constant, I would let the compiler strength reduce that specific division, likely turning it into a multiply and some shifts. </p>
  
  <p>Is there a similar optimization that applies to 2^n+1?</p>
  
  <p>Edit: a here can be an arbitrary 64-bit integer. n takes only a few values between 10 and, say, 25. I can certainly precompute some values for each n, but not for a.</p>