namespace std {
template <class T>
constexpr int popcount(T x) noexcept;
}
概要
立っているビットを数える。popcountは「population count」の略。
テンプレートパラメータ制約
- 型
T
が符号なし整数型であること
戻り値
値x
の、1ビットの数を返す。
例外
投げない
備考
- この関数は、ハードウェア機能として提供されている場合がある
- GCCの組み込み関数として
__builtin_popcount()
、__builtin_popcountl()
、__builtin_popcountll()
が定義されていた - popcountは少なくとも1961年のCPUアーキテクチャから存在している命令であり、NSA (アメリカ国家安全保障局) の要請によって暗号解析のためアーキテクチャに導入された。この命令は幅広い用途に使われる:
- 暗号解析
- エラー訂正 (ECC, Error Correction Code)。ハミング距離 (Hamming Distance) の計算に使用する
- チェスプログラム。チェスではビットでボード情報を保持することが多く、64ビットワードに1ボードの情報が収まる。popcountによって駒の変動計算などができる
- 分子の特徴ベクトル (Molecular Fingerprinting)。分子はなんらかの方法でハッシュ化され、それらがどれくらい似ているかをpopcountで判断する
- Hash Array Mapped Tries (HAMT) アルゴリズム
- ビット配列 (標準では
std::bitset
やstd::vector<bool>
)
例
#include <cassert>
#include <bit>
#include <cstdint>
int main()
{
auto i = static_cast<std::uint32_t>(0b1000'0000'0000'1010'0000'0000'0000'1000u);
int n = std::popcount(i);
assert(n == 4);
}
出力
バージョン
言語
- C++20
処理系
- Clang: 9.0 ✅
- GCC: 9.2 ✅
- Visual C++: ??