How to calculate 2^n-1 efficiently without overflow?

Question

I want to calculate 2ⁿ-1 for a 64bit integer value. What I currently do is this

for(i=0; i<n; i++) r|=1<<i; 

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.

I thought of

  r=(1ULL<<n)-1; 

but it doesn't work for n=64, because << is only defined for values of n up to 63.

---

EDIT: 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.

     r=N2MINUSONE_LUT[n];            3.9 lookup table = fastest, answer by aviraldg r =n?~0ull>>(64 - n):0ull;      5.9 fastest without LUT, comment by Christoph r=(1ULL<<n)-1;                  5.9 Obvious but WRONG!    r =(n==64)?-1:(1ULL<<n)-1;      7.0 Short, clear and quite fast, answer by Gabe r=((1ULL<<(n/2))<<((n+1)/2))-1; 8.2 Nice, w/o spec. case, answer by drawnonward r=(1ULL<<n-1)+((1ULL<<n-1)-1);  9.2 Nice, w/o spec. case, answer by David Lively r=pow(2, n)-1;               99.0 Just for comparison for(i=0; i<n; i++) r|=1<<i;   123.7 My original solution = lame 

I accepted

r =n?~0ull>>(64 - n):0ull; 

as answer because it's in my opinion the most elegant solution. It was Christoph who came up with it at first, but unfortunately he only posted it in a comment. Jens Gustedt added a really nice rationale, so I accept his answer instead. Because I liked Aviral Dasgupta's lookup table solution it got 50 reputation points via a bounty.

Answer 1

Use a lookup table. (Generated by your present code.) This is ideal, since the number of values is small, and you know the results already.

/* lookup table: n -> 2^n-1 -- do not touch */ const static uint64_t N2MINUSONE_LUT[] = { 0x0, 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff, 0x3fff, 0x7fff, 0xffff, 0x1ffff, 0x3ffff, 0x7ffff, 0xfffff, 0x1fffff, 0x3fffff, 0x7fffff, 0xffffff, 0x1ffffff, 0x3ffffff, 0x7ffffff, 0xfffffff, 0x1fffffff, 0x3fffffff, 0x7fffffff, 0xffffffff, 0x1ffffffff, 0x3ffffffff, 0x7ffffffff, 0xfffffffff, 0x1fffffffff, 0x3fffffffff, 0x7fffffffff, 0xffffffffff, 0x1ffffffffff, 0x3ffffffffff, 0x7ffffffffff, 0xfffffffffff, 0x1fffffffffff, 0x3fffffffffff, 0x7fffffffffff, 0xffffffffffff, 0x1ffffffffffff, 0x3ffffffffffff, 0x7ffffffffffff, 0xfffffffffffff, 0x1fffffffffffff, 0x3fffffffffffff, 0x7fffffffffffff, 0xffffffffffffff, 0x1ffffffffffffff, 0x3ffffffffffffff, 0x7ffffffffffffff, 0xfffffffffffffff, 0x1fffffffffffffff, 0x3fffffffffffffff, 0x7fffffffffffffff, 0xffffffffffffffff, }; 

Answer 2

How about a simple r = (n == 64) ? -1 : (1ULL<<n)-1;?