• Class / Function / Type

      std::
    • Header file

      <>
    • Other / All

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

    履歴 編集

    function template
    <bit>

    std::popcount

    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::bitsetstd::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

    処理系

    関連項目

    参照