如何找到比给定数量少2的最大功率
我需要找到比给定数字少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
如何解决这个问题?
改变res =(int)Math.pow(res, 2);
res *= 2;
这将返回2的大于res的下一个幂。
因此,您正在寻找的最终结果将在while结束后最终为res / 2
。
为了防止代码溢出int值空间,你应该/可以将res的类型更改为double / long,任何可以包含比int更高值的值。 最后你必须投一次。
Integer.highestOneBit(n-1);
对于n <= 1
这个问题确实没有意义。 该范围内的操作留给感兴趣的读者。
这是Hacker's Delight中一个很好的比特算法集合。
你可以使用这个hack :
v--; v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; v++; v >>= 1;
为什么不使用日志?
public int largestPowerOf2(int n) { return (int)Math.pow(2, Math.floor(Math.log(n) / Math.log(2)); }
log(n) / log(2)
告诉你2进入一个数字的次数。 通过获取它的底部,获得四舍五入的整数值。
在Integer
中有一个很好的函数,有用, numberOfLeadingZeros
。
有了它,你可以做到
0x80000000 >>> Integer.numberOfLeadingZeros(n - 1);
当n
为0或1时,这是奇怪的事情,但对于那些输入,没有明确定义的“2的最小功率小于n
”。
编辑: 这个答案更好
您可以消除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的最大力量。
public class MathPow { public int largestPowerOf2 (int n) { int res = 2; while (res < n) { res =res*2; } return res; } }
你每次都在调整res ,这意味着你计算2^2^2^2
而不是2^k
。
将评估更改为以下内容:
int res = 2; while (res * 2 < n) { res *= 2; }
更新:
当然,你需要检查int的溢出,在这种情况下检查
而(res <=(n - 1)/ 2)
似乎好多了。
这是我为此目的编写的递归位移方法:
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; }
所以在你的main方法中,让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
从左到右找到第一个设置位,并使所有其他设置位为0。
如果只有1个设置位,则向右移动一个。
public class MathPow { public int largestPowerOf2(int n) { int res = 1; while (res <= (n-1)/2) { res = res * 2; } return res; } }
如果数字是整数,您可以随时将其更改为二进制,然后找出数字位数。
n = (x>>>0).toString(2).length-1
p=2; while(p<=n) { p=2*p; } p=p/2;
如果数字是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));
我在上面看到了另一个BigInteger解决方案,但实际上这很慢。 如果我们要超越整数和更长的话,更有效的方法是
BigInteger nvalue = TWO.pow(BigIntegerMath.log2(value, RoundingMode.FLOOR));
其中TWO
只是BigInteger.valueOf(2L)
和BigIntegerMath
取自Guava。
我认为这是最简单的方法。
Integer.highestOneBit(n-1);
简单的位操作应该有效
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<
有点晚了……
(假设32位数。)
n|=(n>>1); n|=(n>>2); n|=(n>>4); n|=(n>>8); n|=(n>>16); n=n^(n>>1);
说明:
第一个| 确保设置原始顶部位和第二个最高位。 第二个| 确保这两个,以及接下来的两个等等,直到你可能击中所有32位。 即
100010101 – > 111111111
然后我们通过xor’ing 1的字符串删除除了顶部位之外的所有字符串,其中1的字符串向左移动一个,我们最终只得到一个顶部位,然后是0。