最終更新日時: 2026年04月06日 11時49分40秒 (JST)
Akira Takahashi が更新

履歴 編集

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

### 処理系

- Clang: 9.0 ✅
- GCC: 9.2 ✅
- Visual C++: ??

## 関連項目

- `std::bitset::count()`
- `stdc_count_ones` - C互換のビット操作関数

## 参照

- P0553R4 Bit operations
- You Won’t Believe This One Weird CPU Instruction!