如何找到比给定数量少2的最大功率

Question

我需要找到比给定数字少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      

如何解决这个问题？

Answer 1

Integer.highestOneBit(n-1);

对于n <= 1这个问题并没有多大意义.该范围内的操作留给感兴趣的读者.

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

Answer 2

更改res =(int)Math.pow(res, 2);为此res *= 2;将返回大于res的下一个2的幂.
因此,您正在寻找的最终结果将res / 2在片尾结束后终于出现.

为了防止代码溢出int值空间,你应该/可以将res的类型更改为double/long,任何可以包含比int更高值的值.最后你必须投一次.

Answer 3

你可以用这个黑客攻击:

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
v >>= 1;

Answer 4

为什么不使用日志？

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

log(n) / log(2)告诉你2进入一个数字的次数.通过采取它的底部,获得四舍五入的整数值.

Answer 5

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

有了它,你可以做到

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

当n0或1时,哪些奇怪的东西,但对于那些输入,没有明确定义的"2的最大功率小于n".

编辑:这个答案更好

Answer 6

您可以消除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的幂的数,那么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).然后我们将对两个数字进行按位AND. 例:

  10101000
& 10100111
------------
  10100000

我们现在有二进制数10100000.如果我们从它中减1并且我们在两个数字上使用按位AND,我们得到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执行按位AND,即14(二进制1110)和13(二进制1101).

例:

  1110
& 1101
---------
  1100

现在我们有12个,我们只需要消除最后一个最低位.然后,我们再对n和n-1执行按位AND,即12(二进制1100)和11(二进制1011).

例

  1100
& 1011
--------
  1000

我们最终留下8,这是2小于16的最大力量.