最上位ビットを見つける
1. 概要
一部のアルゴリズムは、整数のbinary表現に基づいてアイデアを作成します。 このチュートリアルでは、整数の最上位ビットを見つけるための2つのアルゴリズムを示します。
まず、提供されたアプローチを理解するのに役立ついくつかの定義を提供することから始めます。 その後、素朴なアプローチについて説明し、いくつかの事実を使用して、時間の複雑さを抑えたより良いアプローチを取得します。
2. 定義
非負の整数を10進数から2進数形式に変換することを簡単に思い出してみましょう。 その後、素朴なアプローチを最適化するために後で必要になるビット演算と方程式を紹介します。
2.1. 10進数から2進数への表現
アイデアを説明するための例を提供しましょう。 数値が89で、binary形式を使用して表現するとします。
これを行うための手順を見てください。
数がゼロになるまで、複数のステップを実行します。
結局のところ、答えは、2で割ったときの数値のモジュロを取るときに得られた0と1のリストです。
最上位ビットは、最後に保存するビットであることに注意してください。 同様に、最下位ビットは最初に取得するビットです。
2.2. ビット演算
ほとんどのプログラミング言語は、非負の整数に適用されるビット単位演算をサポートしています。 これらの操作の使用は、特定の数値のバイナリ表現のビットを操作することです。
この記事では、で示される左シフト操作に関心があります。 この操作は、数値のバイナリ形式を特定のビット数だけ左にシフトします。
2.3. 上位ビット
2進数の興味深い点は、次の方程式です。
この式から、次のように結論付けることができます。
これが意味するのは、アクティブ化されたときの各ビットは、それらすべてがアクティブ化されたとしても、すべての小さいビットの合計よりも大きな値を持つということです。 この観察は、後で素朴なアプローチを改善するときに役立ちます。
3. 素朴なアプローチ
素朴なアプローチでは、バイナリ表現のビットを1つずつ抽出します。 各ビットについて、その値をチェックし、最も重要なアクティブなビットを格納します。
素朴なアプローチの実装を見てみましょう。
まず、現在のビットインデックスを示すゼロで初期化します。 また、最上位ビットのインデックスを格納する-1に設定します。
その後、複数のステップを実行します。 各ステップで、2で割った余りをとることにより、現在のビットの値を取得します。 また、2で割って次のステップに進みます。 これらの手順は、セクション2.1で説明した数値のバイナリ表現を取得するのと似ていることに注意してください。
ビットごとに、アクティブ化されているかどうかを確認します。 その場合、そのインデックスをこれまでに見つかった最上位ビットとして格納します。 また、を1つ増やして、次のビットに移動します。
ゼロに達すると、のすべてのビットを繰り返し処理したことを意味します。 この時点で、必要なインデックスを返します。
がゼロの場合、ループは実行されないことに注意してください。 アルゴリズムは-1を返します。これは、アクティブ化されたビットがないことを示します。
素朴なアプローチの複雑さはです。ここで、は必要な非負数です。
4. 二分探索アプローチ
まず、この問題を解決するために二分探索アルゴリズムを使用する背後にある考え方を説明しましょう。 次に、アルゴリズムを実装できます。
4.1. 一般的なアイデア
セクション2.3では、すべてのビットがアクティブ化されている場合でも、各ビットの値がすべての下位ビットの値よりも大きいことに気付きました。 この事実を使用して、最も重要なビットの次のビットを見つけることができます。 次のビットとは、ビットを意味します。ここで、は最も重要なビットです。
線形検索を実行してこのビットを見つけるのではなく、二分探索アルゴリズムを使用できます。
最初に、答えとなる可能性のある最大インデックスを知る必要があります。 この値を。と表記しましょう。 答えは範囲内のどこかにあります。
最も重要なビットの隣のビットを見つけるために、検索範囲の中央をチェックします。 現在の検索範囲がで、中央の値がであると仮定します。
がより大きい場合、これが必要なビットである可能性があります。 この場合、ビットはこれまたは小さいビットのいずれかであると結論付けることができます。 したがって、範囲内のどこかにあります。
ただし、がより大きい場合、このビットは最も重要なビットの次のビットにはなりません。 したがって、ビットのインデックスを増やす必要があるため、検索範囲はになります。
これらのアイデアを使用して、二分探索アプローチを実装しましょう。
4.2. 実装
二分探索アプローチの実装を見てみましょう。
まず、検索範囲として初期化します。 ご覧のとおり、ゼロから始まり、可能な限り最大の答えから始まります。 最も重要なビットの次のビットを検索しているため、に1を追加しました。
また、最上位ビットのインデックスを保持するように初期化します。
二分探索操作の各ステップで、探索範囲の中間点を計算します。 次に、ビットの値が。より大きいかどうかを確認します。 もしそうなら、私たちは可能な答えを持っています。
この場合、これまでのところ、考えられる答えとして、このビットの前のビットを格納します。 また、小さい値をチェックする必要があるため、検索範囲の右側をに移動します。
一方、ビットの値が。より大きくない場合は、検索範囲の左側を。に移動します。 これは、より大きな値を検索する必要があるためです。
最後に、保存された回答を返します。
素朴なアプローチの複雑さはです。ここで、は必要な数です。 その理由は、のビットに対してバイナリ検索操作を実行しているためです。 のビット数はであり、バイナリ検索操作を実行しているため、複雑さはビット数の対数値になります。
5. 例
セクション2.1で説明したのと同じ例を取り上げて、両方のアルゴリズムが最上位ビットを計算する方法を見てみましょう。 その例では、は89に等しかった。
5.1. 素朴なアプローチ
アルゴリズムの手順を説明している表を確認してください。
主に、1つずつビットを抽出しています。 各ステップで、が1に等しい場合、電流をとして保存します。
最終的に、結果が得られます。
5.2. 二分探索アプローチ
二分探索には同様のを使用しますが、8に等しいと仮定します。 アルゴリズムがどれだけうまく機能するか見てみましょう：
各ステップで、範囲の中間点を計算します。 次に、範囲の左側と右側のどちらで答えを探すかを比較して決定します。 また、がより大きい場合は、現在として保存します。
ご覧のとおり、二分探索アプローチでは、比較の数が少なくなりました。
6. 比較
ご覧のとおり、二分探索操作を使用すると、複雑さが軽減されます。 ただし、二分探索操作を使用できるようにするための1つの主要な条件があります。 で初期化するための可能な答えには上限が必要です。
最上位ビットインデックスの上限を見積もることができない場合は、複雑さがそれほど悪くない単純なアプローチを採用する必要があります。
7. 結論
このチュートリアルでは、特定の非負の整数の最上位ビットを見つける問題について説明しました。
与えられた非負の整数のバイナリ表現に関連するいくつかのアイデアを提示しました。 これらのアイデアに基づいて、単純なアプローチを開発し、それを最適化して二分探索アプローチに到達することができました。
最後に、両方の簡単な比較を示し、二分探索アプローチを使用するための要件を示しました。
