bitsetの便利機能・速度・ランダムアクセスの仕様

APG4b¹のビット演算の解説で必要になったので、bitsetの「便利機能」、「実行速度」および「ランダムアクセス方法の違い」について調べてみました。

bitsetの便利機能

bitsetは通常のビット演算では少し面倒な操作を簡単に行えるようになっています。以下に便利機能の表を示します。

記法	動作
`[k]`, `.test(k)`/`.set()`(/`.reset(k)`)	ランダムアクセス
`.flip(k)`	k番目のビットを反転
`cout << bitsetの値`	ビットの形式で標準出力
`.to_string()`	ビットの形式で文字列に変換

bitsetの実行速度

ビット数が少ない場合

1つの整数型で収まる程度にビット数が少ない場合、整数型を直接操作するのと比べて実行速度がどれくらい変わるのかをビット数N=24でシンプルなビット全探索を行うプログラムで調べました。計測に利用したプログラムは記事の末尾に置いておきます。

結果

unsigned int：409ms
bitset：409ms

どちらも実行速度は変わらないという結果になりました。実質ランダムアクセスのみの比較ではありますが、便利さと速度のトレードオフにはなっておらず、常にbitsetを利用しても問題なさそうです。

ビット数が多い場合

ビット数が多い場合に関しては既に比較している記事があったので、リンクと概要を紹介します。

ビット演算の速度比較
- ビット数1000000の場合、シフト演算はarray<bool, N>やvector<char>等の他のコンテナと比べて2倍～3000倍速く、OR演算は190倍～1000倍速い。
ランダムアクセスの比較
- bool[]よりは3倍近く遅いが、vector<bool>よりは少し速い。速度が重要であり、bitsetの便利関数やビット演算を行わない場合はbool[]を使ったほうが良い。

ランダムアクセス方法の違い

bitsetはk番目のビットを操作する場合、.test(k)/.set(k, b)または[k]を用います。動作の違いを以下の表に示します。

記法	動作	境界チェック
.test(k)	k番目のビットの読み込み	あり
.set(k, b)	k番目のビットをbに変更	あり
`[k]`	k番目のビットへの読み書き	なし

[k]は便利ですが境界チェックがなく、kが境界外のときは未定義動作になります。しかもその検出は厄介なことがあるので、複雑な添字操作を行う場合は[]よりもtestやsetを利用したほうが良いでしょう。

検出が厄介な理由

GCCの実装を見るとbitsetはスタック領域上の配列でビット列を管理しており、operator[]では間接的にその配列へアクセスしています。そのためoperator[]を利用して境界外アクセスが発生した場合でも、もともとのビット数が十分多ければAddressSanitizerやgdbでエラーを検知できます。
ただし、ビット数がunsigned longひとつで表現できる場合(通常64以下)は特殊化されており、単にunsigned longを扱っているのと同じような実装になります。そのため不正な添字でもランダムアクセスの際には単なるビット演算しか行われずSegmentation Faultが発生しないので、ツールが検知してくれません。

結論

bitsetは速い・安全・便利。C++でビット演算を行うときは毎回bitsetを利用してもいいかもしれない。
ただし安全に使いたいなら.test(k)/.set(k, b)を使うべし。

計測に使ったプログラム

計測に使ったプログラムは以下のよいうになります。
実行時間はAtCoderのコードテストC++14 (GCC5.4.1)上で複数回実行した結果の平均を取っています。

// integer
#include <bits/stdc++.h>
using namespace std;

int main() {
  const int N = 24;
  unsigned int sum = 0;
  for (int i = 0; i < (1 << N); i++) {
    unsigned int bit = i;
    for (int i = 0; i < N; ++i) {
      if (bit & (1 << i)) {
        sum += i;
      }
    }
  }
  cout << sum << endl;
}

// bitset
#include <bits/stdc++.h>
using namespace std;

int main() {
  const int N = 24;
  unsigned int sum = 0;
  for (int i = 0; i < (1 << N); i++) {
    bitset<N> bit(i);
    for (int i = 0; i < N; ++i) {
      if (bit.test(i)) {
        sum += i;
      }
    }
  }
  cout << sum << endl;
}

僕とあるごんさんで書いてるC++の入門教材 ↩

ブログのとさか

技術的な話をしたりしなかったり

bitsetの便利機能・速度・ランダムアクセスの仕様