Databases
StackOverflow2013
Postsdbo
POHow to calculate 2^n-1 efficiently without overflow?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow to calculate 2^n-1 efficiently without overflow?
    text
    copied!<p>I want to calculate 2<sup>n</sup>-1 for a 64bit integer value. What I currently do is this</p> <pre><code>for(i=0; i&lt;n; i++) r|=1&lt;&lt;i; </code></pre> <p>and I wonder if there is more elegant way to do it. The line is in an inner loop, so I need it to be fast.</p> <p>I thought of</p> <pre><code> r=(1ULL&lt;&lt;n)-1; </code></pre> <p>but it doesn't work for <code>n=64</code>, because <code>&lt;&lt;</code> is only defined for values of <code>n</code> up to 63.</p> <hr> <p><strong>EDIT:</strong> Thanks for all your answers and comments. Here is a little table with the solutions that I tried and liked best. Second column is time in seconds of my (completely unscientific) benchmark.</p> <pre> r=N2MINUSONE_LUT[n]; 3.9 lookup table = fastest, <a href="https://stackoverflow.com/questions/3032951/how-to-calculate-2n-1-efficiently-without-overflow/3032977#3032977">answer</a> by aviraldg r =n?~0ull&gt;&gt;(64 - n):0ull; 5.9 fastest without LUT, <a href="https://stackoverflow.com/questions/3032951/how-to-calculate-2n-1-efficiently-without-overflow/3033004#3033004">comment</a> by Christoph r=(1ULL&lt;&lt;n)-1; 5.9 Obvious but WRONG! r =(n==64)?-1:(1ULL&lt;&lt;n)-1; 7.0 Short, clear and quite fast, <a href="https://stackoverflow.com/questions/3032951/how-to-calculate-2n-1-efficiently-without-overflow/3033004#3033004">answer</a> by Gabe r=((1ULL&lt;&lt;(n/2))&lt;&lt;((n+1)/2))-1; 8.2 Nice, w/o spec. case, <a href="https://stackoverflow.com/questions/3032951/how-to-calculate-2n-1-efficiently-without-overflow/3033900#3033900">answer</a> by drawnonward r=(1ULL&lt;&lt;n-1)+((1ULL&lt;&lt;n-1)-1); 9.2 Nice, w/o spec. case, <a href="https://stackoverflow.com/questions/3032951/how-to-calculate-2n-1-efficiently-without-overflow/3033033#3033033">answer</a> by David Lively r=pow(2, n)-1; 99.0 Just for comparison for(i=0; i&lt;n; i++) r|=1&lt;&lt;i; 123.7 My original solution = lame </pre> <p>I accepted </p> <pre><code>r =n?~0ull&gt;&gt;(64 - n):0ull; </code></pre> <p>as answer because it's in my opinion the most elegant solution. It was <a href="https://stackoverflow.com/users/48015/christoph">Christoph</a> who came up with it at first, but unfortunately he only posted it in a <a href="https://stackoverflow.com/questions/3032951/how-to-calculate-2n-1-efficiently-without-overflow/3033004#3033004">comment</a>. <a href="https://stackoverflow.com/users/366377/jens-gustedt">Jens Gustedt</a> added a really nice rationale, so I accept his answer instead. Because I liked <a href="https://stackoverflow.com/users/152873/aviral-dasgupta">Aviral Dasgupta's</a> lookup table <a href="https://stackoverflow.com/questions/3032951/how-to-calculate-2n-1-efficiently-without-overflow/3032977#3032977">solution</a> it got 50 reputation points via a bounty.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload