1

指数関数の出力が入力値を超えるまでプログラムを実行し続け、それを指数関数の前の出力と比較する必要があります。たとえ疑似コードであっても、どうすればそのようなことをすることができますか?

4

9 に答える 9

5
  1. 与えられた数値から 2 を底とする対数を求める => x := log (2, 入力)
  2. 1で取得した値を上下に丸める => y := round(x), z := round(x) + 1
  3. 2^y, 2^z を見つけて、両方を入力と比較し、より適した方を選択します
于 2012-01-22T23:25:11.573 に答える
2

ループとは別に、コンパイラが nlz 命令をどのようにマップするかによって、より高速になる可能性がある 1 つの解決策もあります。

public int nextPowerOfTwo(int val) {
   return 1 << (32 - Integer.numberOfLeadingZeros(val - 1)); 
}

明示的なループはなく、 を使用したソリューションよりも確実に効率的ですMath.pow。コンパイラがnumberOfLeadingZeros.

これにより、2 の低いべき乗を簡単に取得し、どちらが近いかを比較できます。最後の部分は、私には思われる各ソリューションに対して実行する必要があります。

于 2012-01-22T23:46:10.747 に答える
2

使用している言語に応じて、ビット単位の操作を使用してこれを簡単に行うことができます。入力値に設定された最上位 1 ビットよりも大きい単一の 1 ビットが設定された値、または入力値に設定された最上位 1 ビットが設定された値のいずれかが必要です。

最上位の設定ビットより下のすべてのビットを 1 に設定する場合は、1 を追加すると、2 の次の累乗になります。これを右にシフトして、次に低い 2 の累乗を取得し、2 つの近い方を選択できます。

unsigned closest_power_of_two(unsigned value)
{
    unsigned above = (value - 1); // handle case where input is a power of two
    above |= above >> 1;          // set all of the bits below the highest bit
    above |= above >> 2;
    above |= above >> 4;
    above |= above >> 8;
    above |= above >> 16;
    ++above;                      // add one, carrying all the way through
                                  // leaving only one bit set.

    unsigned below = above >> 1;  // find the next lower power of two.

    return (above - value) < (value - below) ? above : below;
}

他の同様のトリックについては、 Bit Twiddling Hacksを参照してください。

于 2012-01-22T23:49:46.687 に答える
1

x を 1 に設定します。

x < ターゲットの間、x = 2 * x に設定

次に、x または x / 2 のうち、ターゲットに近い方を返します。

于 2012-01-22T23:20:14.060 に答える
0

これはビット単位の解決策です。同数の場合は 2^N と 2^(N+1) の小さい方を返します。これは、log() 関数の呼び出しに比べて非常に高速です。

let mask = (~0 >> 1) + 1

while ( mask > value )
    mask >> 1

return ( mask & value == 0 ) ? mask : mask << 1
于 2012-01-23T04:39:06.397 に答える
0 
public static int neareastPower2(int in) {
    return (int) Math.pow(2, Math.round(Math.log(in) / Math.log(2)));
}
于 2012-01-22T23:45:09.543 に答える
0

入力数値を受け取って答えを返す関数の疑似コードを次に示します。

int findit( int x) {
  int a = int(log(x)/log(2));
  if(x >= 2^a + 2^(a-1))
    return 2^(a+1)
  else
    return 2^a
}
于 2012-01-23T00:35:26.150 に答える
0 
public static int neareastPower2(int in) {
    if (in <= 1) {
        return 1;
    }
    int result = 2;

    while (in > 3) {
        in = in >> 1;
        result = result << 1;
    }

    if (in == 3) {
        return result << 1;
    } else {
        return result;
    }
}
于 2012-01-22T23:40:36.953 に答える
0

簡単な例として、50 の代わりに 5 を入力として使用します。

  • 入力をビット/バイトに変換します。この場合は 101
  • 2 のべき乗を探しているので、答えはすべて 10000...00 (一定量のゼロを含むもの) の形式になります。入力値 (3 ビット) を取得し、100 (3 ビット) と 1000 (4 ビット) の整数値を計算します。整数 100 は入力よりも小さくなり、整数 1000 は大きくなります。
  • 入力と 2 つの可能な値の差を計算し、最小のものを使用します。この場合、100 = 4 (1 の差) であり、1000 = 8 (3 の差) であるため、検索される答えは 4 です。
于 2012-01-22T23:42:10.200 に答える