您可以消除 n 中的最低有效位,直到 n 是 2 的幂。您可以对 n 和 n-1 使用按位运算符 AND,这将消除 n 中的最低有效位,直到 n 是 2 的幂。如果最初 n 是 2 的幂,那么你所要做的就是将 n 减 1。
public class MathPow{
public int largestPowerOf2(int n){
if((n & n-1) == 0){ //this checks if n is a power of 2
n--; //Since n is a power of 2 we have to subtract 1
}
while((n & n-1) != 0){ //the while will keep on going until n is a power of 2, in which case n will only have 1 bit on which is the maximum power of 2 less than n. You could eliminate the != 0 but just for clarity I left it in
n = n & n-1; //we will then perform the bitwise operation AND with n and n-1 to eliminate the least significant bit of n
}
return n;
}
}
解释:
当您有一个数字 n(不是 2 的幂)时,小于 n 的 2 的最大幂始终是 n 中的最高有效位。在数字 n 是 2 的幂的情况下,小于 n 的 2 的最大幂是 n 中唯一打开的位之前的位。
例如,如果我们有 8(即 2 的 3 次方),它的二进制表示是 1 0 00,粗体的 0 将是 n 之前 2 的最大幂。由于我们知道二进制中的每个数字都代表 2 的幂,那么如果我们将 n 作为 2 的幂,那么小于 n 的 2 的最大幂将是它之前的 2 的幂,即位在 n 中唯一的位之前。
对于一个数字 n,它不是 2 的幂,也不是 0,我们知道在二进制表示中 n 会有不同的位,这些位只会表示 2 的各种幂的总和,其中最重要的是成为最重要的位。然后我们可以推断出 n 只是最高有效位加上其他一些位。由于 n 以一定长度的位表示,并且最高有效位是我们可以用该位数表示的 2 的最高幂,但它也是我们可以用这么多位表示的最低数,那么我们可以得出结论最高有效位是比 n 低的 2 的最高幂,因为如果我们添加另一个位来表示 2 的下一个幂,我们将得到大于 n 的 2 的幂。
例子:
例如,如果我们有 168(二进制为 10101000),while 将取 168 并减去 1,即 167(二进制为 10100111)。然后我们将对两个数字进行按位与。
例子:
10101000
& 10100111
------------
10100000
我们现在有二进制数 10100000。如果我们从中减去 1,然后对这两个数字使用按位与,我们得到 10000000,即 128,即 2 的 7 次方。
例子:
10100000
& 10011111
-------------
10000000
如果 n 本来是 2 的幂,那么我们必须从 n 中减去 1。例如,如果 n 是 16,即二进制 10000,我们将减去 1,得到 15,即二进制 1111,然后我们将它存储在 n 中(这就是 if 所做的)。然后我们进入while,它使用n和n-1进行按位运算符AND,这将是15(二进制1111)和14(二进制1110)。
例子:
1111
& 1110
--------
1110
现在我们剩下 14。然后我们对 n 和 n-1 执行按位与,即 14(二进制 1110)和 13(二进制 1101)。
例子:
1110
& 1101
---------
1100
现在我们有 12 个,我们只需要消除最后一个最低有效位。同样,我们然后对 n 和 n-1 执行按位与,即 12(二进制 1100)和 11(二进制 1011)。
例子
1100
& 1011
--------
1000
我们最后剩下 8,这是 2 小于 16 的最大幂。