整数のセットビット数を数える
1. 概要
このチュートリアルでは、整数のセットビット数をカウントする問題について説明します。 まず、問題を定義します。 次に、それを説明するための例を示します。
最後に、それを解決するための3つの異なるアプローチを紹介します。
2. 問題の定義
整数があり、のバイナリ表現で1に等しいビット数をカウントする必要があるとします。
理解を深めるために、次の例を見てみましょう。 整数が与えられたら、その中のセットビットの数を数えましょう。
そのバイナリ表現を見ると、次のようになります。 1に等しい2つのビットがあります。 したがって、与えられた例に対する答えはです。
3. 素朴なアプローチ
このアプローチの主なアイデアは、指定された数値のバイナリ表現の各ビットを反復処理し、それがアクティブ化されているかどうかを確認することです。答えを1つ増やします。 それ以外の場合はスキップします。
与えられた数がゼロより大きい限り、 bitwise を取り、との間で演算することにより、の最初のビットを取得します。 最初のビットがオンの場合、答えを1つ増やします。 その後、2で割って最初のビットを取り除きます。
数がゼロに等しくなると、答えは指定された整数の設定ビット数になります。
3.1. アルゴリズム
アルゴリズムの実装を見てみましょう。
最初に、整数で設定されたビット数を返す関数を宣言します。 関数には1つのパラメーターがあり、設定されたビットをカウントするために指定された数を表します。
まず、設定されたビット数を格納することを宣言します。 次に、指定された数値がゼロより大きい場合、つまりまだカウントしていないビットが設定されているため、との間の演算を実行して最初のビットを取得します。
第三に、私たちが得た最初のビットがに等しい場合、それは最初のビットがオンになっていることを意味します。 そこで、答えを1つ増やします。 次に、のバイナリ表現を1ずつ右にシフトして、チェックした最初のビットを取り除くために、で除算します。
最後に、指定された数に設定されたビット数を格納するを返します。
3.2. 複雑さ
このアルゴリズムの時間計算量はです。ここで、は指定された数値です。 この複雑さの背後にある理由は、の各ビットを反復処理し、ビットがあるためです。
4. ジャンプオンワンズアプローチ
このアプローチの主なアイデアは、指定された数の最後のセットビットを取得し、セットビットの数を1つ増やしてから、そのビットをオフにすることです。 数がゼロより大きい間、その操作を繰り返します。
指定された数値がゼロより大きい場合、との間の演算を実行することにより、の最後のセットビットを取得します。
数がゼロに等しくなると、答えは指定された整数の設定ビット数になります。
4.1. アルゴリズム
アルゴリズムの実装を見てみましょう。
最初に、前のアプローチと同じ関数を宣言します。これにより、指定された数のセットビット数が返されます。
次に、設定されたビット数を格納することを宣言します。 次に、指定された数値がゼロより大きい場合、つまりまだカウントしていないセットビットがある場合、との間の演算を実行して最後のセットビットを取得します。
その後、それを削除するためにそのビットを減算し、次に1ずつ増やします。
最後に、は指定された数の設定ビット数を返します。
4.2. 複雑さ
このアルゴリズムの時間計算量はです。ここで、は、最良のシナリオと最悪のシナリオで発生する可能性のある、指定された数の2進表現の1の数です。
この複雑さの理由は、数値の最後のセットビットを取得し、その数値がバイナリ表現のビットをオンにしている限り、それを削除するためです。
5. ハミングウェイトアプローチ
The ここでの主なアイデアは、指定された数値のバイナリ表現をブロックに分割することです。ブロックには、対応するブロックのセットビットの合計が格納されます。 次に、奇数ブロックを偶数ブロックから分離し、それらを互いに上に配置し、それらを合計して、古いブロックの2倍のサイズの新しいブロックを取得し、設定されたビットの合計を隣接する対応する古いブロックに格納します。
まず、サイズ1のブロックから始めます。 奇数ビットと偶数ビットを取得します。 次に、それらを互いに上に配置し、それらを合計して、対応する隣接ビットの合計を格納するサイズ2のブロックを取得します。
次に、サイズ2のブロックに対して同じプロセスを実行します。 奇数ブロックを偶数ブロックから分離し、それらを互いに上に配置し、それらを合計してサイズ4のブロックを取得します。 各ブロックには、対応する4ビットの合計が格納されます。 サイズ4のブロックでも同じことを行い、サイズ8、8から16、および16から32のブロックを取得します。
最後に、サイズのブロックに達すると、指定された整数のすべてのビットの合計を取得します。これは、指定された数のすべての設定ビットの合計を取得することを意味します。
5.1. アルゴリズム
アルゴリズムの実装を見てみましょう。
最初に、指定された整数のセットビット数を取得する関数があります。
次に、次の手順を実行します。
- との間の演算を実行して奇数ビットを取得します。これは、に等しいバイナリ表現を持ちます。ここで、偶数ビットを取得し、結果を奇数ビットに揃えるために、のバイナリ表現を1つ右にシフトします。 ‘で操作を行います。 両方の演算の合計は、それぞれが対応する付加ビットの合計を格納するサイズ2のブロックを持つ新しい数値を返します。
- 前の手順で同じ操作を実行してサイズ2のブロックを取得しますが、代わりに、バイナリ表現が等しい数のを取得し、バイナリ表現を2だけ右にシフトして、偶数のブロックを取得します。
- 同じ操作を行うことでサイズ4のブロックを取得しますが、代わりに、彼のバイナリ表現がに等しい数を使用し、バイナリ表現を4だけ右にシフトして、偶数のブロックを取得します。
- 同じ操作を行うことでサイズ8のブロックを取得しますが、代わりに、彼の2進表現がに等しい数を使用し、2進表現を8だけ右にシフトして、偶数のブロックを取得します。
- 同じ操作を行うことでサイズ16のブロックを取得しますが、代わりに、彼のバイナリ表現がに等しい数を使用し、バイナリ表現を16だけ右にシフトして、偶数のブロックを取得します。
最後に、数値は、指定された数値のビット全体の合計であるサイズのブロック内のすべてのビットの合計に等しくなります。
5.2. 複雑さ
このアルゴリズムの時間計算量は次のとおりです。この複雑さの理由は、一定数の算術演算を実行するためです。
6. 結論
この記事では、整数のセットビット数を見つける問題を紹介しました。
まず、問題を説明する例を示しました。 次に、それを解決するための3つの異なるアプローチを検討しました。
最後に、それぞれのアプローチの時間計算量が前のアプローチよりも優れている状態で、それらの実装について説明しました。
