为什么这个位操作return这个结果？

Question

有一个java代码：

private static final int tableSizeFor(int c) {
    int n = c - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : n + 1;
}

结果是：min(2 和 >=c 的时间)

例如，如果c为5，则结果为8，如果c为16，则结果为16。

我已经按照算法计算出来了，但我不知道如何理解这个算法，谁能解释清楚，谢谢。

Answer 1

这是在寻找 2 的幂 >= c。

它通过填充最上面的 1 下面的所有 1 来做到这一点。例如101010 变成 111111 然后在末尾加 1 使它成为 1000000，即。 2 的幂。

它从减 1 开始，因此 2 的幂保持不变。

我不确定为什么它会检查 n >= Integer.MAX_VALUE，因为根据定义 int 不能比 MAX_VALUE >。也许这段代码是从最初使用 long n 的算法复制而来的。

请注意 n > 1 << 30 这将溢出并产生 1 而不是 MAX_VALUE。

为什么这个位操作return这个结果？

Why this bit manipulation return this result?

java

algorithm

bit