Как эффективно рассчитать 2 ^ n-1 без переполнения?

Question

Я хочу вычислить 2 ⁿ -1 для 64-битного целочисленного значения.То, что я сейчас делаю, это

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

, и мне интересно, есть ли более элегантный способ сделать это.Линия находится во внутреннем цикле, поэтому мне нужно, чтобы она была быстрой.

Я думал о

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

, но она не работает для n=64, потому что <<определяется только для значений от n до 63.

---

РЕДАКТИРОВАТЬ: Спасибо за все ваши ответы и комментарии.Вот небольшой столик с решениями, которые я попробовал и которые понравились мне больше всего.Второй столбец - это время в секундах моего (совершенно ненаучного) теста.

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>>(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<<n)-1;                  5.9 Obvious but WRONG!   
r =(n==64)?-1:(1ULL<<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<<(n/2))<<((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<<n-1)+((1ULL<<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<n; i++) r|=1<<i;   123.7 My original solution = lame

Я принял

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

в качестве ответа, потому что, на мой взгляд, это самое элегантное решение.Сначала это было Кристоф , но, к сожалению, он опубликовал это только в комментарии . Jens Gustedt добавил действительно хорошее обоснование, поэтому я принимаю его ответ вместо этого.Поскольку мне понравилось справочная таблица Aviral Dasgupta решение , он получил 50 очков репутации за вознаграждение.

Answer 1

Я думаю, что проблема, которую вы видите, вызвана тем, что (1<<n)-1 оценивается как (1<<(n%64))-1 на некоторых чипах. Особенно, если n является или может быть оптимизировано как константа.

Учитывая это, вы можете сделать множество незначительных изменений. Например:

((1ULL<<(n/2))<<((n+1)/2))-1;

Вам нужно будет измерить, чтобы узнать, быстрее ли это, чем специальный корпус 64:

(n<64)?(1ULL<<n)-1:~0ULL;

Answer 2

Ub = universe in bits = lg(U):
high(v) = v >> (Ub / 2)
low(v) = v & ((~0) >> (Ub - Ub / 2))  // Deal with overflow and with Ub even or odd