如何有效地计算2 ^ n-1而不溢出？

Question

我想为64位整数值计算2 ⁿ -1.我现在做的是这个

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, 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

我接受

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

作为答案,因为在我看来,这是最优雅的解决方案.克里斯托夫起初是想出来的,不幸的是他只在评论中发表了 这篇文章.Jens Gustedt添加了一个非常好的理由,所以我接受了他的回答.因为我喜欢Aviral Dasgupta的查找表解决方案,它通过赏金获得了50个声望点.

Answer 1

使用查找表.(由您现有的代码生成.)这是理想的,因为值的数量很少,并且您已经知道了结果.

/* 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

简单r = (n == 64) ? -1 : (1ULL<<n)-1;怎么样？

Answer 3

如果你想在溢出之前获得给定位数的最大值,请尝试

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

通过将移位分成两部分(在这种情况下,两个63位移位,因为2 ^ 64 = 2*2 ^ 63),减去1然后将两个结果加在一起,您应该能够进行计算而不会溢出64位数据类型.

Answer 4

if (n > 64 || n < 0)
  return undefined...

if (n == 64)
  return 0xFFFFFFFFFFFFFFFFULL;

return (1ULL << n) - 1;

Answer 5

我最喜欢aviraldg的回答.为了摆脱C99中的"ULL"东西,我会这样做

static inline uint64_t n2minusone(unsigned n) {
   return n ? (~(uint64_t)0) >> (64u - n) : 0;
}

要看这是有效的

• uint64_t保证宽度恰好为64位
• 因此,"uint64_t类型的零"的位否定恰好是64位
• 无符号值的右移保证是一个逻辑移位,所以从左边用零填充所有内容
• 具有等于​​或大于宽度的值的移位是未定义的,所以是的,您必须至少执行一个条件以确保您的结果
• 内联函数(或者如果你愿意,还可以转换为uint64_t)使这种类型安全; a unsigned long long将来可能是128位宽的值
• 一个static inline功能应该无缝地在联主叫方没有任何开销