4. popcount

最終更新日時(UTC):
が更新

履歴 編集

function template
<bit>

std::popcount(C++20)

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

処理系

関連項目

参照