bitset | Programming Place Plus C++編【標準ライブラリ】 第13章

C++編【標準ライブラリ】 第13章 bitset

先頭へ戻る

この章の概要

この章の概要です。


bitset

bitset は、ビット配列を提供するクラステンプレートです。つまり、各要素が 0 か 1 にしかならない配列を表現できます。使用するには、<bitset> という名前の標準ヘッダをインクルードする必要があります。

bitset は、次のように定義されています。

namespace std {
    template <size_t Bits>
    class bitset {
    };
}

テンプレート仮引数 Bits は、ノンタイプテンプレート仮引数(【言語解説】第22章)で、ここにビット配列のビット総数(サイズ)を指定します。例えば、bitset<10> とすることで、10個の bool値を持った配列を定義できます。

このような仕組みであるため、bitset では動的なメモリ割り当ては行われません

ビット総数をテンプレート仮引数で指定しているため、後から変更することはできません。この点が、bitset の大きな制約となっています。もし、動的にビット総数を変更するような使い方が必要であれば、vector<bool>(第5章)を使用する方法があります(ただし、vector<bool> は普通の vector とは違うことに注意)。

動的な bitset を実装したものに、boost の dynamic_bitset があります。

また、例えば、bitset<10> と bitset<20> は別の型であることにも注意して下さい。


生成と初期化

bitset には、複数のコンストラクタが定義されているので、様々な方法でインスタンス化できます。

#include <bitset>
#include <string>

typedef std::bitset<10> TestBitset;

int main()
{
    std::string s("10110110");

    TestBitset bset1;           // すべて 0
    TestBitset bset2(0xFF);     // 整数値のビット表現を使って初期化
    TestBitset bset3(s);        // 文字列による表現から初期化
    TestBitset bset4(s, 4);     // 文字列による表現から初期化。開始位置を指定。
    TestBitset bset5(s, 4, 2);  // 文字列による表現から初期化。開始位置と文字数を指定。
}

bset1 のように、デフォルトコンストラクタによって生成された場合、すべてのビットは 0 で初期化されます。

bset2 では、unsigned long型を1つ指定し、そのビット表現通りのビット配列が作られます。上の例では「0xFF」を渡しているので、「11111111」というビット配列になります。

C++11 では、型が unsigned long long型に変更されています。

bset3、bset4、bset5 は、std::string型の文字列を指定し、その表現からビット配列を作ります。bset4 では開始位置を、bset5 では更に文字数を指定しています。なお、bitset のサイズに満たない場合、不足分は 0 で埋められ、bitset よりも長い場合は、余分な指定は無視されます。つまり、bset3 は「0010110110」、bset4 は「0000000110」、bset5 は「0000000001」になります。

この文字列には '0' か '1' だけが含まれていなければなりません。もし他の種類の文字が含まれていたら、std::invalid_argument例外第17章)が送出されます。

ところで、bset3、bset4、bset5 で使われているコンストラクタは、テンプレートコンストラクタ(【言語解説】第25章)になっているため、例えば「TestBitset bset3("10110110")」のように、const char*型の文字列を指定すると、コンパイルエラーになります。そのため、明示的に「TestBitset bset3(std::string("10110110"))」といったように指定する必要があります。

C++11 では部分的に解決されており、bset3、bset4 のパターンならば、直接 const char*型を渡せます。これは、第1引数が const T*型のテンプレートコンストラクタが追加された結果です。

C++11 (生成と初期化)

C++11 で、コンストラクタ周りは強化されています。

C++11 では、整数値を1つ渡すタイプのコンストラクタにおいて、その型が unsigned long型から、unsigned long long型に変更されています。

文字列から初期化するタイプでは、末尾に2つのデフォルト実引数が追加されており、false を表す文字と、true を表す文字を指定できるようになりました。デフォルト実引数はそれぞれ '0' と '1' なので、省略すれば、従来通りの挙動になります。

std::string s("TFTTFTTF");

TestBitset bset6(s, 0, s.length(), 'F', 'T');  // F は 0、T は 1 のこと

また、第1引数に std::string ではなく、const char* を渡せる形のコンストラクタが追加されています。こちらは、第1引数から順に「文字列」「文字数」「false を表す文字」「true を表す文字」となっており、「開始位置」は指定できなくなっています。

TestBitset bset7("TFTTFTTF", s.length(), 'F', 'T');  // F は 0、T は 1 のこと

最後に、デフォルトコンストラクタに constexpr指定子(【言語解説】第18章)が追加されており、bitset をリテラル型として扱えるようになりました。

破棄

bitset は、動的なメモリ確保を行っていないので、デストラクタにおいても特に何も行われません。

サイズ

bitset においての「サイズ」は、ビット総数のことを指します。

bitset<0> としていない限り、要素が無いという状態はあり得ないので、emptyメンバ関数は存在せず、 あるのは sizeメンバ関数だけです。

#include <bitset>
#include <iostream>

int main()
{
    std::bitset<0> bset1;
    std::bitset<10> bset2;
    std::bitset<100> bset3;

    std::cout << bset1.size() << "\n"
              << bset2.size() << "\n"
              << bset3.size() << std::endl;
}

実行結果

0
10
100

C++11 (sizeメンバ関数の constexpr関数化)

C++11 の sizeメンバ関数は、constexpr関数に変更されています。

入出力

bitset は、標準入出力ストリーム(第26章【言語解説】第5章)と直接連携できるようになっています。具体的には、std::istream を使って直接入力することができ、std::ostream を使って直接出力できます。

#include <bitset>
#include <iostream>

typedef std::bitset<10> TestBitset;

int main()
{
    TestBitset bset;

    std::cin >> bset;
    std::cout << bset << std::endl;
}

実行結果

1101  (←入力内容)
0000001101

入力に関しては、'0' か '1' のいずれかの文字が登場すると、そこで読み取りが停止します。また、1文字も読み取れなかった場合は、使用した入力ストリームに std::ios::failbit が設定されます。

要素の設定

bitset内の特定のビットを設定するには、setメンバ関数か、[]演算子を使います。

#include <bitset>
#include <iostream>

typedef std::bitset<8> TestBitset;

int main()
{
    TestBitset bset(0xF0);  // 11110000

    bset.set(3);            // 3ビット目を true に
    bset.set(7, false);     // 7ビット目を false に
    bset[0] = true;         // 0ビット目を true に

    std::cout << bset << std::endl;
}

実行結果

01111001

setメンバ関数には3つのオーバーロードがあり、そのうちの2種類を使用しています。第1引数に、対象のビット位置を指定します。第2引数がある場合は、第2引数に指定した bool型の値をセットし、無い場合は true をセットします。

[]演算子の場合は、[]内にビット位置を指定すると、そのビット位置を指す参照を返します(厳密にはやや違います。コラム参照)。そのため、=演算子を使って、bool値を与えてやれば、ビットを設定できます。

[]演算子が返すのは、bitset<>::reference型の一時オブジェクトです。ポインタにせよ、参照にせよ、指し示す先は「バイト」であり「ビット」では無いので、このように間に1つクラスを挟むことで、間接的に実現しています。

正常な範囲外のビット位置を指定した場合、setメンバ関数は std::out_of_range例外(第17章)を送出するのに対し、[]演算子は未定義の動作になります。

setメンバ関数のもう1つの形式を使うと、全ビットがすべて true になります。

#include <bitset>
#include <iostream>

typedef std::bitset<8> TestBitset;

int main()
{
    TestBitset bset(0xF0);  // 11110000

    bset.set();

    std::cout << bset << std::endl;
}

実行結果

11111111

このように、setメンバ関数が、基本的には true を設定するものであり、引数が2つあるバージョンでだけ true か false かを選択できるのに対し、false を設定するための resetメンバ関数があります。こちらは、2つのオーバーロード形式があります。

#include <bitset>
#include <iostream>

typedef std::bitset<8> TestBitset;

int main()
{
    TestBitset bset(0xF0);  // 11110000

    bset.reset();
    std::cout << bset << std::endl;

    bset.set();     // すべて true
    bset.reset(3);
    std::cout << bset << std::endl;
}

実行結果

00000000
11110111

引数のない resetメンバ関数は、全ビットを false に設定します。引数のある resetメンバ関数は、指定したビット位置だけを false に設定します。resetメンバ関数は、setメンバ関数と同様、有効な範囲外のビット位置を指定すると、std::out_of_range例外を送出します。

要素の取得

bitset内の特定のビットの状態を取得するには、[]演算子か、testメンバ関数を使います。

#include <bitset>
#include <iostream>

typedef std::bitset<8> TestBitset;

int main()
{
    TestBitset bset(0xF0);  // 11110000

    std::cout << bset[0] << "\n"
              << bset[4] << "\n"
              << bset.test(7) << std::endl;
}

実行結果

0
1
1

[]演算子の場合は、[]内にビット位置を指定すると、そのビット位置の値を返します。要素を設定する場合の []演算子と違い、取得の際の []演算子の戻り値は、単なる bool型の値です。

testメンバ関数の場合も基本的に同じです。引数はビット位置で、そのビット位置の値を返します。

両者の違いは、正常な範囲外のビット位置を指定した場合で、testメンバ関数は std::out_of_range例外(第17章)を送出するのに対し、[]演算子は未定義の動作になります。

C++11 (取得用の operator[] の constexpr関数化)

C++11 では、要素の値を取得する []演算子 (operator[]) が、constexpr関数に変更されています。

ビット演算

bitset は、各種のビット単位の演算が簡単に行えるようになっています。

まず、&演算子による AND演算、|演算子による OR演算、~演算子による NOT演算、^演算子による XOR演算、<<演算子による左シフト演算、>>演算子による右シフト演算がそれぞれ可能です。また、~演算子以外は、複合代入演算子が使用できます。

#include <bitset>
#include <iostream>

typedef std::bitset<8> TestBitset;

int main()
{
    TestBitset bset(0xF0);           // 11110000

    bset &= 0xAA;
    std::cout << bset << std::endl;  // 10100000

    bset |= 0x0F;
    std::cout << bset << std::endl;  // 10101111

    bset ^= 0xFF;
    std::cout << bset << std::endl;  // 01010000

    bset = ~bset;
    std::cout << bset << std::endl;  // 10101111

    bset <<= 4;
    std::cout << bset << std::endl;  // 11110000

    bset >>= 2;
    std::cout << bset << std::endl;  // 00111100
}

実行結果

10100000
10101111
01010000
10101111
11110000
00111100

また、flipメンバ関数を使用すると、任意のビット、あるいはすべてのビットを反転させることができます。

#include <bitset>
#include <iostream>

typedef std::bitset<8> TestBitset;

int main()
{
    TestBitset bset(0xF0);           // 11110000

    bset.flip();
    std::cout << bset << std::endl;  // 00001111

    bset.flip(2);
    std::cout << bset << std::endl;  // 00001011

    bset[5].flip();
    std::cout << bset << std::endl;  // 00101011
}

実行結果

00001111
00001011
00101011

3つ目のパターンでは、[]演算子が返した参照に対して呼び出しています。この形の場合は、[]演算子の時点で、対象のビット位置が特定されているので、そのビットだけが反転します。

要素の設定」の項のコラムにあるように、[]演算子が返しているのは、bitset<>::reference型の一時オブジェクトです。上記の例は、bitset<>::reference::flipメンバ関数を呼び出している訳です。

また、ビットの状態を調べるメンバ関数が幾つか存在します。

countメンバ関数を使うと、値が 1 (true) になっているビットの総数を取得できます。

値が 1 (true) になっているビットがあるかどうかを、anyメンバ関数で調べられます。逆に、値が 1 (true) になっているビットが存在しないかどうかを、noneメンバ関数で調べられます。

#include <bitset>
#include <iostream>

typedef std::bitset<8> TestBitset;

int main()
{
    TestBitset bset(0xF0);           // 11110000

    std::cout << std::boolalpha
              << bset.count() << "\n"
              << bset.any() << "\n"
              << bset.none() << std::endl;

    bset.reset();                    // 00000000

    std::cout << std::boolalpha
              << bset.count() << "\n"
              << bset.any() << "\n"
              << bset.none() << std::endl;
}

実行結果

4
true
false
0
false
true

C++11 (allメンバ関数)

C++11 では、すべてのビットが 1 (true) になっているかどうかを調べる allメンバ関数が追加されています。

TestBitset bset(0xF0);  // 10100000
std::cout << std::boolalpha << bset.all() << std::endl;  // false
bset.set();  // 11111111
std::cout << std::boolalpha << bset.all() << std::endl;  // true

型変換

to_stringメンバ関数を使うと、bitset が保持しているビット列を、文字列化して返すことができます。

std::cout に、bitset のオブジェクトをそのまま渡すと、文字列化したビット列が出力されますが、これは、to_stringメンバ関数を呼び出すことで実現されています。

#include <bitset>
#include <iostream>

typedef std::bitset<8> TestBitset;

int main()
{
    TestBitset bset(0xF0);           // 11110000

    std::string s = bset.to_string<char, std::char_traits<char>, std::allocator<char> >();

    std::cout << s << std::endl;
}

実行結果

11110000

呼び出している箇所を見ると分かるように、テンプレート実引数の指定が必要です。to_stringメンバ関数は、関数テンプレート(メンバ関数テンプレート)であり、std::basic_stringクラステンプレートに指定するテンプレート実引数を、そのままの順で指定するようになっています。関数自体に引数が無いので、テンプレート実引数を推測させることもできず、1つ1つ指定するしかありません(【言語解説】第9章)。そのため、正直、かなり使いづらいと言わざるを得ません。

C++11 で、関数テンプレートのテンプレート仮引数に、デフォルトテンプレート実引数が与えられるようになったため(【言語解説】第9章)、それに合わせて、to_stringメンバ関数の宣言も変更されており、使いやすくなりました。

C++11 (to_stringメンバ関数の宣言の変更)

C++11 では、to_stringメンバ関数のテンプレート仮引数に、デフォルトテンプレート実引数が設定されており、戻り値が、char型を当てはめた std::basic_string で良ければ、特にテンプレート実引数を指定しなくて良くなりました。

std::string s = bset.to_string();

また、デフォルト実引数が2つ追加されており、false を表す文字と、true を表す文字を指定できるようになりました。デフォルト実引数はそれぞれ '0' と '1' なので、省略すれば、従来通りの挙動になります。

TestBitset bset(0xF0);
std::string s = bset.to_string('F', 'T');  // TTTTFFFF


また、bitset が保持しているビット列を、整数値で返す to_ulongメンバ関数があります。これは、名前の通り、unsigned long型で返しますが、もし表現できないビット列だった場合には、std::overflow_error例外第17章)が送出されます。

#include <bitset>
#include <iostream>

typedef std::bitset<8> TestBitset;

int main()
{
    TestBitset bset(0xF0);           // 11110000

    std::cout << bset.to_ulong() << std::endl;
}

実行結果

240

C++11 (to_ullongメンバ関数の追加)

C++11 では、結果を unsigned long long型(C言語編第19章)で返す、to_ullongメンバ関数が追加されています。表現できないビット列だった場合には、std::overflow_error例外が送出されます。

std::cout << bset.to_ullong() << std::endl;


練習問題

問題① bitset を利用して、整数値を、2進数の文字列表現に変換する関数を作成して下さい。


解答ページはこちら

参考リンク



更新履歴

'2018/4/5 VisualStudio 2013 の対応終了。

'2018/4/2 「VisualC++」という表現を「VisualStudio」に統一。

'2018/1/5 コンパイラの対応状況について、対応している場合は明記しない方針にした。

'2017/7/30 clang 3.7 (Xcode 7.3) を、Xcode 8.3.3 に置き換え。

'2017/3/25 VisualC++ 2017 に対応。

≪更に古い更新履歴を展開する≫



前の章へ(第12章 priority_queue)

次の章へ(第14章 イテレータ)

C++編のトップページへ

Programming Place Plus のトップページへ


はてなブックマーク Pocket に保存 Twitter でツイート Twitter をフォロー
Facebook でシェア Google+ で共有 LINE で送る rss1.0 取得ボタン RSS