1. 概要

このチュートリアルでは、数値が2の累乗であるかどうかを確認する問題について説明します。

まず、問題を定義します。 次に、それを説明するための例を示します。

最後に、この問題を解決するための3つの異なるアプローチを紹介します。

2. 問題の定義

正の整数が与えられた場合、それが2の累乗であるかどうかを確認する必要があります。

次の例を見てみましょう。

  • 2の累乗。
  • 2の累乗。
  • 2の累乗ではありません。
  • 2の累乗ではありません。

3. ループアプローチ

3.1. 本旨

2つの数値の累乗を確認すると、2進数で（1の後にゼロが続く）のような形式で記述されていることがわかります。 したがって、このアプローチの主なアイデアは、1に達するまで、数値の末尾から0を削除し続けることです。

1に達すると、後続のゼロをすべて削除した後、数値がに等しくなるかどうかを確認します。 もしそうなら、それは与えられた数が2の累乗であることを意味します。

3.2. アルゴリズム

実装を見てみましょう：

最初は、偶数でゼロより大きい限り、のバイナリ表現の最後にゼロがあることを意味します。 この場合、2で割って、バイナリ表現を右にシフトします（末尾のゼロを削除します）。 前の条件の1つが偽になると、ループから抜け出します。

結局、がに等しくなる場合、それは与えられた数が2の累乗であることを意味するので、を返します。 それ以外の場合は、を返します。

3.3. 複雑さ

このアルゴリズムの複雑さはです。ここで、は指定された数値です。 この複雑さの背後にある理由は、指定された数値のすべてのビットを反復処理するためです。 ビット数はに等しい。

4. 二分探索アプローチ

4.1. 本旨

このアプローチの主なアイデアは、二分探索を使用して、等しい2の累乗が存在するかどうかを見つけることです。 さらに、検索は数値の指数部分で行われます。 したがって、現在の2の累乗が、未満の場合は、より大きなものを探します。

一方、現在の2の電力がよりも大きい場合は、より小さな電力を見つけようとします。 を作る力を見つけたら、真に戻ります。

ただし、二分探索が終了し、に等しい2の累乗が見つからない場合、それは2の累乗ではないことを意味します。

4.2. アルゴリズム

実装を見てみましょう：

最初に、二分探索の境界を宣言します。 は可能な最小電力であり、ゼロに等しくなります。 逆に、は可能な最大電力であり、（のビット数）に等しくなります。

次に、境界が境界以下である限り、数値の指数部分として、2の生成された累乗がに等しいかどうかを確認します。 もしそうなら、trueを返します。 それ以外の場合は、現在の数が。未満かどうかを確認します。 この場合、より大きな力を探します。 そうでない場合は、より小さな電力を探します。

最後に、に等しい2の累乗が見つからない場合は、を返します。

4.3. 複雑さ

このアルゴリズムの複雑さはです。ここで、は指定された数値です。

ここでの複雑さは、二分探索の複雑さと同じです。これは、チェックしたい可能性のある力があるためです。

5. ビットマスクアプローチ

5.1. 本旨

ここでの主なアイデアは、のバイナリ表現を利用することです。 さらに、2つの数値の累乗の2進表現は、のような形式になります。 したがって、2の累乗から1つを削除すると、のようになります。 次に、との間でビット単位および演算を実行すると、が2の累乗である場合、結果はゼロに等しくなります。 そうでなければ、そうではありません。

5.2. アルゴリズム

実装を見てみましょう：

2の最小の累乗が1に等しいため、がゼロより大きいかどうか、およびとの間のビット単位の演算がゼロに等しいかどうかを確認します。 もしそうなら、それは2の累乗であることを意味します。 そうでなければ、それは2の累乗ではありません。

5.3. 複雑さ

このアルゴリズムの複雑さはです。これは、1つの操作、つまり操作のみを実行しているためです。

6. 結論

この記事では、数値が2の累乗であるかどうかを確認する問題を紹介しました。

まず、問題を説明する例を示しました。 次に、この問題を解決するための3つの異なるアプローチを示しました。 最後に、それぞれのアプローチの時間計算量が前のアプローチよりも優れている状態で、それらの実装について説明しました。