C++/標準ライブラリ/bitset

はじめに

std::bitsetクラステンプレートは、固定長のビット配列を表現するためのコンテナクラスです。個々のビットに対して設定や参照ができ、ビット演算や入出力ストリームをサポートしています。メモリ上で効率的にビット列を扱う必要がある場合に便利なクラスです。

#include <bitset>
#include <iostream>

auto main() -> int {
    std::bitset<8> bits(0b10101010);  // 8ビットの初期値
    bits.set(2);                      // 3番目のビットを1に設定
    std::cout << bits << std::endl;   // 出力: 10101110

    return 0;
}

bitsetクラステンプレート

テンプレートパラメータ

std::bitsetはクラステンプレートで、テンプレート引数Nでビット数を指定します。Nには0以上の整数値を指定でき、そのビット数のビット配列が確保されます。

コンストラクタ

constexpr bitset() noexcept;: 全てのビットを0で初期化します。
constexpr bitset(unsigned long long val) noexcept;: 最下位ビットからの初期値を指定して初期化します。
template<class CharT, ...> bitset(const basic_string<CharT,...>& str, ...);: 文字列からビット列を初期化します。文字列中の'0'と'1'以外の文字は無視されます。
template<class CharT, ...> bitset(basic_string_view<CharT, ...> str, ...);: 文字列ビューから初期化するコンストラクタ(C++17)。
template<class CharT, ...> bitset(const CharT* str, ...);: Null終端の文字列からビット列を初期化します。

メンバ関数

ビット操作

bitset& operator&=(const bitset& rhs) noexcept;: ビット毎のAND演算を行います。
bitset& operator|=(const bitset& rhs) noexcept;: ビット毎のOR演算を行います。
bitset& operator^=(const bitset& rhs) noexcept;: ビット毎のXOR演算を行います。
bitset& set() noexcept;: 全てのビットを1にセットします。
bitset& set(size_t pos, bool val = true);: 指定した位置posのビットをvalでセットします。
bitset& reset() noexcept;: 全てのビットを0にリセットします。
bitset& reset(size_t pos);: 指定した位置posのビットを0にリセットします。
bitset operator~() const noexcept;: ビット毎の否定を取ったビットセットを返します。
bitset& flip() noexcept;: 全ビットを反転させます。
bitset& flip(size_t pos);: 指定した位置posのビットを反転させます。

シフト操作

bitset& operator<<=(size_t pos) noexcept;: ビット列を左シフトします。
bitset& operator>>=(size_t pos) noexcept;: ビット列を右シフトします。
bitset operator<<(size_t pos) const noexcept;: 左シフトしたビットセットを返します。
bitset operator>>(size_t pos) const noexcept;: 右シフトしたビットセットを返します。

要素アクセス

bool operator[](size_t pos) const;: 指定した位置posのビットを参照します。
reference operator[](size_t pos);: 指定した位置posのビットをreferenceオブジェクトで返します。このオブジェクトを使ってビットの設定や反転ができます。
unsigned long to_ulong() const;: ビット列をunsigned long型に変換して返します。
unsigned long long to_ullong() const;: ビット列をunsigned long long型に変換して返します。
basic_string<CharT,Traits,Allocator> to_string(...) const;: ビット列を文字列に変換して返します。

その他のメンバ関数

size_t count() const noexcept;: ビット列中の1の個数を返します。
size_t size() const noexcept;: ビット列の長さ(ビット数)を返します。
bool operator==(const bitset& rhs) const noexcept;: 2つのビット列が等しいかを判定します。
bool test(size_t pos) const;: 指定した位置posのビットが1かどうかをテストします。
bool all() const noexcept;: 全てのビットが1かどうかを判定します。
bool any() const noexcept;: 1つ以上のビットが1かどうかを判定します。
bool none() const noexcept;: 全てのビットが0かどうかを判定します。

非メンバ関数

bitset<N> operator&(const bitset<N>&, const bitset<N>&) noexcept;
bitset<N> operator|(const bitset<N>&, const bitset<N>&) noexcept;
bitset<N> operator^(const bitset<N>&, const bitset<N>&) noexcept;: それぞれビット毎のAND、OR、XOR演算を行い、新しいbitsetオブジェクトを返します。

bitset::referenceクラス

bitsetクラスには内部でreferenceクラスが定義されています。これはビットの参照オブジェクトで、個々のビットにアクセスしたり、ビットの設定・反転を行うのに使用します。

std::bitset<8> bits(0b10101010);
std::bitset<8>::reference ref = bits[3]; // 4番目のビットの参照を取得
ref.flip(); // ビットを反転

referenceクラスには以下のメンバ関数が定義されています。

reference& operator=(bool x) noexcept;: ビットにbool値を代入します。
reference& operator=(const reference& rhs) noexcept;: 別のビット参照オブジェクトの値を代入します。
bool operator~() const noexcept;: ビットの否定を取った値を返します。
operator bool() const noexcept;: ビットの値をbool型に変換して返します。
reference& flip() noexcept;: ビットを反転させます。

入出力演算子

std::bitsetには、ビット列と文字列の相互変換を行う入出力ストリーム演算子がサポートされています。

ostream& operator<<(ostream& os, const bitset<N>& x);: ビット列を"0"と"1"の文字列として出力ストリームに出力します。
istream& operator>>(istream& is, bitset<N>& x);: 入力ストリームから"0"と"1"の文字列を読み取り、ビット列に変換して格納します。

std::hash特殊化

std::bitsetには、クラステンプレートstd::hashの特殊化が定義されています。これにより、std::unordered_setやstd::unordered_mapなどの非順序関数射影コンテナでbitsetを使用できます。

#include <bitset>
#include <unordered_set>

auto main() -> int {
    std::unordered_set<std::bitset<8>> set;
    set.insert(0b10101010);  // bitsetをハッシュキーとして使用

    return 0;
}

使用例

ビットフラグの実装

std::bitsetを使えば、ビットフラグを効率的に実装できます。各フラグに対応するビットを1または0にセットすることで、複数のフラグの組み合わせを表現できます。

enum OptionFlags {
    OF_NONE             = 0,
    OF_CASE_INSENSITIVE = 1 << 0,
    OF_MULTILINE        = 1 << 1,
    OF_DEBUG            = 1 << 2
};

std::bitset<4> options;
options.set(OF_CASE_INSENSITIVE);
options.set(OF_DEBUG);

if (options.test(OF_CASE_INSENSITIVE)) {
    // 大文字小文字を区別しない
}

enum class でなく昔ながらの enum を使っているのは

#include <bitset>

enum class OptionFlags {
    NONE = 0,
    CASE_INSENSITIVE = 1 << 0,
    MULTILINE = 1 << 1,
    DEBUG = 1 << 2
};

std::bitset<4> options;
options.set(static_cast<std::size_t>(OptionFlags::CASE_INSENSITIVE));
options.set(static_cast<std::size_t>(OptionFlags::DEBUG));

if (options.test(static_cast<std::size_t>(OptionFlags::CASE_INSENSITIVE))) {
    // 大文字小文字を区別しない
}

とキャストが煩雑になるからです

ビット演算

std::bitsetは、ビット単位の論理演算をサポートしています。これを使えば、ビットマスクの生成やビット列の結合、特定のビットパターンの検出などができます。

std::bitset<8> mask(0b10101010);
std::bitset<8> data(0b11110000);

std::bitset<8> result = mask & data; // ビット毎のAND演算
// result: 00100000

ビットパターンの検索・置換

std::bitsetでビット列を表現し、その値を元にビットパターンの検索や置換を行うこともできます。例えば、32ビットのIPアドレスをビット列で表して、ネットワークアドレスを求めるといった処理が可能です。

std::bitset<32> ip_addr("192.168.1.10"); // IPアドレスをビット列で表す
std::bitset<32> subnet_mask("255.255.255.0"); // サブネットマスク

std::bitset<32> network_addr = ip_addr & subnet_mask;
// network_addr: 192.168.1.0 (ネットワークアドレス)

ビット操作と性能

std::bitsetは内部でビットをパッキングしてメモリ効率を高めています。このため、単一のビットへのアクセスには若干のオーバーヘッドがかかりますが、一度にビット列全体を処理する場合は非常に効率的です。

ビット演算の複雑度は定数時間ですが、シフト操作はビットサイズに比例します。コンパイラは一般に、ビット演算に対して良い最適化を行うため、性能上の問題はほとんどありません。

まとめ

std::bitsetはビット列を効率的に扱うためのコンテナクラスです。固定長ビット配列を表現でき、ビット単位の論理演算やシフト操作、入出力などがサポートされています。ビットフラグの実装やビットマスク処理などに適しており、適切に使えば高速で無駄のない処理が可能になります。一方で、単一ビットアクセスのオーバーヘッドには注意が必要です。

bit

C++
bitset

charconv