2

我遇到了一段代码，用于查找大于 32 位整数 n 的 2 的最小幂...

n+=(n==0);
n--;
n|=n>>1;
n|=n>>2;
n|=n>>4;
n|=n>>8;
n|=n>>16;
n++;

现在它是如何工作的？我尝试在 n=100 的每一步之后以 base-2 打印数字，但这没有多大意义。其背后的逻辑是什么？

4

3 回答 3

3

这段代码n用二进制1s 填充给定数字的所有最低有效位，然后将结果增加 ，从而1实现请求的结果。例如，对于输入101，位操作将产生111，并且在增加之后1将变为1000(8)，这实际上是大于101(5) 的 2 的最小幂。

更新：实际上，这是对手动设置每个 lsb 位的简单方法的优化。为什么这种优化能达到相同的结果是一个更广泛范围内的不同问题，超出了这个问题。

于 2013-01-12T07:18:52.210 回答
3

实际上，它找到大于或等于 2 的最小幂，n它适用于 32 位无符号数。

  • 第一行只是以与 1 相同的方式处理 0（以一种有点混乱的方式编写）
  • 第二行说明“或等于”，如果一个数字恰好是 2 的幂，我们将其缩短一点。
  • 接下来的几行确保所有低位都设置为 1。首先我们右移 1 并执行逻辑或。效果是现在最高位和紧随其后的位设置为 1。现在通过移位 2 执行相同操作，使最高 4 位变为 1，依此类推。
  • 最后我们得到一个比 2 的幂小 1 的数字，我们只需加 1。
于 2013-01-12T07:22:13.190 回答
0

除了 icepack 的回答：正如这里所解释的，算法计算1 << (floor(log_2(n - 1)) + 1).

于 2013-01-12T07:21:27.713 回答