12

我需要找到小于给定数字的 2 的最大幂。
我卡住了,找不到任何解决方案。

代码:

public class MathPow {
   public int largestPowerOf2 (int n) {
        int res = 2;        
        while (res < n) {
            res =(int) Math.pow(res, 2);
        }
        return res;
   }
}

这不能正常工作。

测试输出:

Arguments Actual Expected
-------------------------
9         16     8       
100       256    64      
1000      65536  512     
64        256    32      

如何解决这个问题?

4

20 回答 20

42
Integer.highestOneBit(n-1);

因为n <= 1这个问题真的没有意义。在该范围内做什么留给感兴趣的读者。

这是Hacker's Delight中比特旋转算法的一个很好的集合。

于 2013-06-29T11:28:41.753 回答
12

更改res =(int)Math.pow(res, 2);res *= 2;这将返回大于 res 的 2 的下一个幂。
因此,您正在寻找的最终结果最终将res / 2在一段时间结束之后。

为了防止代码溢出 int 值空间,您应该/可以将 res 的类型更改为 double/long,任何可以容纳比 int 更高的值的东西。最后,您将不得不施放一次。

于 2013-06-29T10:06:50.437 回答
12

你可以使用这个位黑客

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
v >>= 1;
于 2013-06-29T10:10:31.997 回答
11

为什么不使用日志?

public int largestPowerOf2(int n) {
    return (int)Math.pow(2, Math.floor(Math.log(n) / Math.log(2));
}

log(n) / log(2)告诉你 2 进入一个数字的次数。通过取它的地板,让你的整数值四舍五入。

于 2013-06-29T10:17:08.550 回答
7

有一个很好的功能Integer很有帮助,numberOfLeadingZeros.

有了它你可以做到

0x80000000 >>> Integer.numberOfLeadingZeros(n - 1);

哪个是 0 或 1 时会发生奇怪的事情n,但是对于这些输入,没有明确定义的“小于 2 的最大幂n”。

编辑:这个答案更好

于 2013-06-29T10:17:14.683 回答
7

您可以消除 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 的最大幂。

于 2015-10-12T19:51:55.683 回答
4

您每次都在平方res2^2^2^2 ,这意味着您计算而不是2^k.
将您的评估更改为以下内容:

int res = 2;
while (res * 2 < n) {
    res *= 2;
}

更新:

当然,您需要检查int的溢出,在这种情况下检查

而 (res <= (n - 1) / 2)

似乎好多了。

于 2013-06-29T10:08:04.093 回答
3
public class MathPow {
   public int largestPowerOf2 (int n) {
        int res = 2;        
        while (res < n) {
                res = res * 2;
        }
        return res;
   }
}
于 2013-06-29T10:08:33.180 回答
3

这是我为此目的编写的递归位移位方法:

public static int nextPowDown(int x, int z) {
    if (x == 1)
        return z;
    return nextPowDown(x >> 1, z << 1);
} 

或更短的定义:

public static int nextPowTailRec(int x) {
    return x <= 2 ? x : nextPowTailRec(x >> 1) << 1;
}

所以在你的主要方法中让z参数总是相等1。可惜这里没有默认参数:

System.out.println(nextPowDown(60, 1));                // prints 32
System.out.println(nextPowDown(24412, 1));             // prints 16384
System.out.println(nextPowDown(Integer.MAX_VALUE, 1)); // prints 1073741824
于 2015-07-19T12:28:15.423 回答
3

有点晚了,但是...

(假设 32 位数。)

n|=(n>>1);
n|=(n>>2);
n|=(n>>4);
n|=(n>>8);
n|=(n>>16);
n=n^(n>>1);

解释:

第一个 | 确保设置了原始最高位和第二高位。第二| 确保这两个以及接下来的两个是等等,直到您可能达到所有 32 位。IE

100010101 -> 111111111

然后,我们通过将 1 的字符串与 1 的字符串向左移一位进行异或运算来删除除最高位之外的所有位,最后我们只得到最高位后跟 0。

于 2018-02-15T21:07:36.533 回答
2

从左到右找到第一个设置位,并使所有其他设置位为 0。

如果只有 1 个设置位,则右移一位。

于 2013-06-29T10:07:22.767 回答
2

我认为这是最简单的方法。

Integer.highestOneBit(n-1);

于 2017-06-03T20:53:45.523 回答
1
public class MathPow
{
   public int largestPowerOf2(int n)
   {
        int res = 1;        
        while (res <= (n-1)/2)
        {
            res = res * 2;
        }

        return res;
   }
}
于 2016-05-25T06:14:42.317 回答
1

如果数字是整数,您可以随时将其更改为二进制,然后找出位数。

n = (x>>>0).toString(2).length-1
于 2017-07-22T06:40:33.263 回答
0
p=2;
while(p<=n)
{
    p=2*p;
}
p=p/2;
于 2014-08-08T16:35:32.443 回答
0

如果这个数字是 2 的幂,那么答案是显而易见的。(只是位移)如果不好也可以通过位移来实现。

在二进制表示中找到给定数字的长度。(二进制中的 13 = 1101 ;长度为 4)

然后 将 2 移动 (4-2) // 4 是给定数字的二进制长度

下面的java代码将为BigIntegers解决这个问题(所以基本上适用于所有数字)。

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        

    String num = br.readLine();
    BigInteger in = new BigInteger(num);
    String temp = in.toString(2);

    System.out.println(new BigInteger("2").shiftLeft(temp.length() - 2));
于 2014-08-24T07:48:56.070 回答
0

我在上面看到了另一个 BigInteger 解决方案,但这实际上很慢。如果我们要超越整数和长整数,一种更有效的方法是

BigInteger nvalue = TWO.pow(BigIntegerMath.log2(value, RoundingMode.FLOOR));

TWO简单的在哪里BigInteger.valueOf(2L)

取自BigIntegerMath番石榴。

于 2015-12-13T02:02:42.360 回答
0

简单的位操作应该可以工作

 public long largestPowerOf2 (long n)
 {      
 //check already power of two? if yes simply left shift
    if((num &(num-1))==0){
        return num>>1;
    }

  // assuming long can take 64 bits     
    for(int bits = 63; bits >= 0; bits--) {
        if((num & (1<<bits)) != 0){
            return (1<<bits);
        }
    }
    // unable to find any power of 2
    return 0;   
  }
于 2017-10-17T12:51:24.780 回答
0
/**
 * Find the number of bits for a given number. Let it be 'k'.
 * So the answer will be 2^k.
 */
public class Problem010 {

  public static void highestPowerOf2(int n) {
    System.out.print("The highest power of 2 less than or equal to " + n + " is ");
    int k = 0;
    while(n != 0) {
      n = n / 2;
      k++;
    }

    System.out.println(Math.pow(2, k - 1) + "\n");
  }

  public static void main(String[] args) {
    highestPowerOf2(10);
    highestPowerOf2(19);
    highestPowerOf2(32);
  }

}
于 2019-05-01T12:58:03.323 回答
0
if(number>=2){

    while(result < number){
        result *=2;
    }
        result = result/ 2;
     System.out.println(result);
    }
于 2021-07-18T13:48:00.523 回答