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

このビットハックを使用できます：

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 に答える
12

Change res =(int)Math.pow(res, 2); to res *= 2; This will return the next power of 2 greater than res.
The final result you are looking for will therefore finally be res / 2 after the while has ended.

To prevent the code from overflowing the int value space you should/could change the type of res to double/long, anything that can hold higher values than int. In the end you would have to cast one time.

于 2013-06-29T10:06:50.437 に答える
11

Why not use logs?

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

log(n) / log(2) tells you the number of times 2 goes into a number. By taking the floor of it, gets you the integer value rounding down.

于 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 に答える
4

You are squaring res each time, meaning you calculate 2^2^2^2 instead of 2^k.
Change your evaluation to following:

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

Update:

Of course, you need to check for overflow of int, in that case checking

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

seems much better.

于 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 に答える
2

Find the first set bit from left to right and make all other set bits 0s.

If there is only 1 set bit then shift right by one.

于 2013-06-29T10:07:22.767 に答える
0

上記の別の BigInteger ソリューションを見ましたが、実際にはかなり遅いです。integer と long を超える場合のより効果的な方法は、

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

TWO単純にどこですかBigInteger.valueOf(2L)

BigIntegerMathグアバから採取されます。

于 2015-12-13T02:02:42.360 に答える
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 に答える