C++ 2 <= n 的最大幂

Question

如何计算两个 <= 某个数 n 的最大幂？

现在我正在使用 floor(log(n)/log(2)+.05) 但它似乎对所有 n 都不可靠。有什么更干净/不受舍入误差影响的东西吗？

Answer 1

我假设这个数字是无符号的。您可以使用二进制表示的知识。

该数字将是在相同 MSB 位置为 1 且全为零的数字。

下面的循环会帮助你。

do {
    y = x;
    x = x&(x-1);
}while(x);
return y;

其中 x 是原始数字，y 是结果。

分支免费代码如下。

unsigned flp2(unsigned x) {
  x = x| (x>>1);
  x = x| (x>>2);
  x = x| (x>>4);
  x = x| (x>>8);
  x = x| (x>>16);
return x - (x>>1);
}

或(依靠循环展开，所有现代编译器都可以做到)

unsigned log2(unsigned x)
{
  for (int i = 0; i < std::numeric_limits<unsigned>::digits; i*=2)
     x |= (x>>i);
  return x - (x>>1);
}

来源:Hacker's Delight。