ビットセット内の特定の位置以下のセット ビットを効率的にカウントするにはどうすればよいですか?

ある位置以下のセット ビットを効率的にカウントする

問題ステートメント:

std::bitset任意のビット値とビット位置 X (0 ～ 63) を使用して、位置 X 以下のビットをカウントする最も効率的な方法を決定します。X のビットが設定されていない場合は 0 を返します。

最適化されたソリューション:

次の C コードは、指定された範囲内のセット ビットを効率的にカウントする、高度に最適化された x86 ASM を生成します。範囲:

#include <bitset>

int popcount_subset(std::bitset<64> bits, int pos) {
    int high_bits_to_eliminate = 63 - pos;
    bits <<= high_bits_to_eliminate & 63; // Shift to place desired bits at the top
    return (bits[63] ? ~0ULL : 0) & bits.count(); // Broadcast high bit or return 0, then popcount
}

実装の詳細:

1. シフト操作: ビットセットは 63 - 位だけ左にシフトされ、必要なビットを 64 ビット レジスタの先頭に追加します。これにより、カウントから不要なビットが削除されます。
2. ビット ブロードキャスト: シフトされたビットセットの上位ビットは、算術右シフトを使用してすべてのビット位置にブロードキャストされます。これにより、上位ビットが設定されている (つまり、pos のビットが設定されている) 場合はすべてのビットが設定され、それ以外の場合はすべてのビットがクリアされるマスクが作成されます。
3. Conditional Popcount: AND 演算ビットセットとマスクを組み合わせます。 pos のビットが設定されている場合、マスクは ~0ULL になり、元のポップカウントになります。それ以外の場合、マスクは 0 になり、ポップカウントは 0 になります。
4. 最適な ASM: このコードは、ハードウェア ポップカウント命令とビット ブロードキャストを利用して、64 ビット アーキテクチャ上で効率的な x86 ASM を生成します。

利点:

• 指定された範囲内のセット ビットをカウントするのに効率的です。
• 次の方法で任意のビットセット サイズに対して機能します。それに応じて定数を調整します。
• 多くの環境で高度に最適化された ASM を生成します。 x86-64 や ARM64 などのアーキテクチャ。
• 未定義の動作を行わずに、pos がビットセット サイズを超えるケースを処理します。

以上がビットセット内の特定の位置以下のセット ビットを効率的にカウントするにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。