Javaで指定された数より少ない2の最大の累乗

投稿日: 2022-10-29 2022-10-29
タグ: Algorithms, Math

1. 概要

この記事では、与えられた数よりも小さい2の最大の累乗を見つける方法を見ていきます。

この例では、サンプル入力9を使用します。 2 ⁰は1であり、与えられた入力より2の累乗が2であることがわかる、最も有効性の低い入力です。したがって、1より大きい入力のみが有効であると見なされます。

2. 素朴なアプローチ

1である2⁰から始めましょう。入力よりも小さい数値が見つかるまで、数値に2を掛け続けます。

public long findLargestPowerOf2LessThanTheGivenNumber(long input) {
    Assert.isTrue(input > 1, "Invalid input");
    long firstPowerOf2 = 1;
    long nextPowerOf2 = 2;
    while (nextPowerOf2 < input) {
        firstPowerOf2 = nextPowerOf2;
        nextPowerOf2 = nextPowerOf2 * 2;
    }
    return firstPowerOf2;
}

サンプルinput=9のコードを理解しましょう。

firstPowerOf2 の初期値は1で、nextPowerOf2は2です。ご覧のとおり、2 <9が真であり、whileループに入ります。

最初の反復では、 firstPowerOf2 は2であり、nextPowerOf2は2*2=4です。ここでも4<9なので、whileループを続けましょう。

2回目の反復では、 firstPowerOf2 は4で、nextPowerOf2は4*2=8です。今8<9、続けましょう。

3回目の反復では、 firstPowerOf2 は8で、nextPowerOf2は8*2=16です。 while条件16<9はfalseであるため、whileループから抜け出します。 8は2の最大の累乗であり、9未満です。

コードを検証するためにいくつかのテストを実行してみましょう。

assertEquals(8, findPowerOf2LessThanTheGivenNumber(9));
assertEquals(16, findPowerOf2LessThanTheGivenNumber(32));

ソリューションの時間計算量はO（log2（N））です。この例では、log ₂（9）=3回繰り返しました。

3. Math.logを使用する

2を底とする対数は、数値を2で再帰的に除算できる回数を示します。つまり、数値のlog2は2の累乗を示します。これを理解するためにいくつかの例を見てみましょう。

log ₂（8）=3およびlog₂（16）=4。一般に、y = log ₂ xであることがわかります。ここで、x = 2 ^yです。

したがって、2で割り切れる数が見つかった場合は、その数から1を引くと、その数が2の累乗であるシナリオを回避できます。

Math.logはlog₁₀です。 log ₂（x）を計算するには、式log ₂（x）= log ₁₀（x）/ log 10[X96Xを使用できます。 ]（2）

それをコードに入れましょう：

public long findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(long input) {
    Assert.isTrue(input > 1, "Invalid input");
    long temp = input;
    if (input % 2 == 0) {
        temp = input - 1;
    }
    long power = (long) (Math.log(temp) / Math.log(2));
    long result = (long) Math.pow(2, power);
    return result;
}

サンプル入力を9とすると、tempの初期値は9です。

9％2は1なので、 temp変数は9です。ここでは、9/2の余りを与えるモジュロ除算を使用しています。

log ₂（9）を見つけるには、log ₁₀（9）/ log ₁₀（2）= 0.95424 / 0.30103〜=3を実行します。

これで、resultは2³、つまり8になります。

コードを確認しましょう：

assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(9));
assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(32));

実際には、 Math.pow は、アプローチ1で行ったのと同じ反復を実行します。したがって、このソリューションの場合も、時間計算量はO（Log2（N））であると言えます。

4. ビット単位の手法

このアプローチでは、ビット単位のシフト手法を使用します。まず、数値を表す4ビットがあることを考慮して、2の累乗の2進表現を見てみましょう。

2 ⁰	1	0001
2 ¹	2	0010
2 ²	4	0100
2 ³	8	1000

よく見ると、1 のバイトを左にシフトすることで、2の累乗を計算できることがわかります。すなわち。 2 ²は、1×2桁の左シフトバイトなどです。

ビットシフト技術を使用してコーディングしましょう：

public long findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(long input) {
    Assert.isTrue(input > 1, "Invalid input");
    long result = 1;
    long powerOf2;
    for (long i = 0; i < Long.BYTES * 8; i++) {
        powerOf2 = 1 << i;
        if (powerOf2 >= input) {
            break;
        }
        result = powerOf2;
    }
    return result;
}

上記のコードでは、8バイトまたは64ビットを使用するデータ型としてlongを使用しています。したがって、2の累乗を2 ⁶⁴まで計算します。ビットシフト演算子を使用しています << 2の力を見つけるために。サンプル入力9の場合、4 ^thの反復後、 powerOf2 =16およびresult = 8の値で、16>としてループから抜け出します。 9入力。

コードが期待どおりに機能しているかどうかを確認しましょう。

assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(9));
assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(32));

このアプローチの最悪の場合の時間計算量は、最初のアプローチで見たものと同様に、やはりO（log2（N））です。ただし、このアプローチは、ビットシフト演算が乗算と比較してより効率的であるため、より優れています。

5. ビット単位のAND

次のアプローチでは、この式 2n AND 2n -1 =0を使用します。

それがどのように機能するかを理解するためにいくつかの例を見てみましょう。

4のバイナリ表現は0100、で、3は0011です。

これらの2つの数値に対してビット単位のAND演算を実行してみましょう。 0100および0011は0000です。 2の累乗とそれよりも小さい数についても同じことが言えます。それぞれ1000、 0111 として表される16（2 ⁴）と15を取りましょう。ここでも、これら2つのビットごとのANDが0になることがわかります。また、これら2以外の数値に対するAND演算は、0にはならないとも言えます。

ビットごとのANDを使用してこの問題を解決するためのコードを見てみましょう。

public long findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(long input) { 
    Assert.isTrue(input > 1, "Invalid input");
    long result = 1;
    for (long i = input - 1; i > 1; i--) {
        if ((i & (i - 1)) == 0) {
            result = i;
            break;
        }
    }
    return result;
}

上記のコードでは、入力よりも少ない数値をループします。数値のビットごとのANDが見つかり、数値1がゼロである場合は常に、数値が2の累乗になることがわかっているため、ループから抜け出します。この場合、サンプル input 9の場合、 i =8およびi – 1=7のときにループから抜け出します。

それでは、いくつかのシナリオを確認しましょう。

assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(9));
assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(32));

このアプローチの最悪の場合の時間計算量は、入力が正確な2乗の場合、O（N / 2）です。ご覧のとおり、これは最も効率的な解決策ではありませんが、同様の問題に取り組むときに役立つ可能性があるため、この手法を知っておくとよいでしょう。

6. 結論

与えられた数よりも小さい2の最大の累乗を見つけるためのさまざまなアプローチを見てきました。また、ビット演算によって計算が単純化される場合があることにも気づきました。

この記事の単体テストを含む完全なソースコードは、GitHubのにあります。

getdocs

13036