念のために説明します。最上位ビットは数値の単一ビットであり、2の最大次数を担当します。 つまり、これは最大の2のべき乗であり、数を超えていません。 多くの場合を避けるために、ここでは1〜2 ^ 31-1の範囲の自然数を扱っていると仮定します。 さらに、確率論に深く入り込まないようにするために、最上位ビットを決定する必要がある数は、可能な数のいずれかである可能性が高いと仮定します。
まず第一に、最も簡単な先着順アルゴリズムを検討してください。 2の累乗をすべて調べて、それらから最大数を選択します。 ここで、明らかに、このプロパティの単調性を利用することができます。つまり、2のある程度が数値を超えない場合、それは1度未満であり、さらには超えません。 したがって、このメソッドは非常に簡単に記述できます。
int bit1(int x) { int t = 1 << 30; while (x < t) t >>= 1; return t; }
int bit1(int x) { int t = 1 << 30; while (x < t) t >>= 1; return t; }
（ここではjavaを使用していますが、コードのネイティブ性により、誰にとっても明確になると思います）
それがどれくらいの時間機能するか見てみましょう。 等しい確率の数値が示された間隔のいずれかであると仮定した場合、1/2の確率で、つまりxが2 ^ 30以上であると判明した場合、whileループは複数回機能しません。 1/4の確率で、つまり、xが2 ^ 29から2 ^ 30-1の範囲にある場合、サイクルは1回動作します。 などなど。 これは、サイクルが平均で半分の時間を満たすことを意味することを理解するのは簡単です。 これは平均ではかなり良いですが、最悪の場合は悪いです：数値x = 1では、サイクルは30回すべて動作します。
次のアルゴリズムは、この迷惑から解放されています。 むしろ、仕事全般の不確実性はありません。 最初にコードをデモンストレーションしてから、それがどのように機能するかを説明します。
int bit2(int x) { x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; return x - (x >> 1); }
int bit2(int x) { x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; return x - (x >> 1); }
したがって、数値x = 000001bbbbbbを指定します（数値内の必要なビット数に従わなかったため、bは任意のビットを意味します）。 それから
x == 000001bbbbbb x >> 1 == 0000001bbbb x | x >> 1 == 0000011bbbb
したがって、最古のユニットの後の最初のアクションは、それがどこにあっても、次を配置します。 2番目は、理解できるように、これら2つの背後にさらに2つを配置します。 第三-別の4（ある場合、どこに置くか）。 などなど。 したがって、最上位以降のすべてのビットの数は単一です。 そして、x-（x >> 1）が正しい答えを与えることは明らかです。
3番目のアルゴリズムは、動作時間にentirely意性がないわけではありませんが、最悪の場合、最初のアルゴリズムよりもはるかに高速に動作します。 これはビン検索に基づいています 。 たとえば、16番目の中間ビットを取り、16番目の若いビットの最上位ビットがあるかどうかの条件を形成してみましょう。 この条件がx <1 << 16であることは明らかです。したがって、テスト結果を保存する必要があります。
int t = 1; if (x >= 1 << 16) t <<= 16;
int t = 1; if (x >= 1 << 16) t <<= 16;
もちろん、tをさらに8ビット、次に4、2、1ずつ移動できるかどうかを確認する必要があります。
int bit3(int x) { int t = 1; if (x >= t << 16) t <<= 16; if (x >= t << 8) t <<= 8; if (x >= t << 4) t <<= 4; if (x >= t << 2) t <<= 2; if (x >= t << 1) t <<= 1; return t; }
int bit3(int x) { int t = 1; if (x >= t << 16) t <<= 16; if (x >= t << 8) t <<= 8; if (x >= t << 4) t <<= 4; if (x >= t << 2) t <<= 2; if (x >= t << 1) t <<= 1; return t; }
そのため、2番目と3番目のアルゴリズムは、最初のアルゴリズムよりも平均して長く動作します（直接実験で確認され、3番目のアルゴリズムが2番目よりもわずかに速く動作するという事実によって確認されます）。
さらに、注意すべき点が1つあります。 最初の方法は、マジック定数1 << 30を使用します。その使用法は、数字が1から2 ^ 31-1のいずれかである可能性が高いという事実に基づいています。数字が小さい場合、定数を減らすことができます。 たとえば、数値が1〜100000の場合、int t = 1 << 17で開始できます。しかし、メソッドが使用される数値がわからない場合はどうでしょうか。 理論的には2 ^ 31-1に等しくても、実際には1000以下である場合、int t = 1 << 30に設定する必要があり、この方法（再び、実験で確認）が機能します次の2つよりも大幅に長くなります。 つまり、最初の方法は長時間動作する場合があるだけでなく、平均してより長い時間動作することもあります。 その動作時間は予測不能です。 これらの問題はすべて、他の2つの方法には当てはまりません。
最後に、別のニュアンス。 上記のアルゴリズムのうち3つは、正確に2のべき乗-2 ^ kという形式の数を返します。 しかし、正確にkを見つける必要がある場合はどうでしょうか？ 1番目と3番目のメソッドは、次数自体ではなく指数を与えるように簡単に変換できます。 最初のアルゴリズムは少し速く動作し始め、3番目のアルゴリズムは少し長くなります。 しかし、2番目のアルゴリズムはこれを完全に不可能です。 したがって、2番目のアルゴリズムにも固有のマイナスがあります。
PS最初のアルゴリズムは明白すぎて著者の問題を提起できません。2番目のアルゴリズムは比較的有名なオリンピアードプログラマーから私に促され、3番目のアルゴリズムは私が思いついたものですが、それは唯一のものではなく、確かに最初のものではありません。