3. サイズを動的に変更できるビット集合

最終更新日時:
が更新

履歴 編集

サイズを動的に変更できるビット集合

サイズを指定する

dynamic_bitset

サイズ固定のビット集合であるstd::bitset に対して、boost::dynamic_bitset はサイズを実行時に変更できるビット集合である。

インデックス

コンストラクタ、もしくはメンバ関数resize()でビット集合のサイズを指定できる。

#include <boost/dynamic_bitset.hpp>
#include <cassert>
#include <iostream>
using namespace std;

int main()
{
    boost::dynamic_bitset<> bs(3);  // サイズ3のビット集合(デフォルト値は全てのビットが0)
    assert(bs.size() == 3); 
    cout << bs << endl;   // -> 000

    bs.resize(5);         // サイズを5に変更
    assert(bs.size() == 5);
    cout << bs << endl;   // -> 00000
}

ビットの値を設定する

メンバ関数set/reset、[ ]演算子でビットの値を設定できる。

#include <boost/dynamic_bitset.hpp>
#include <iostream>
using namespace std;
int main()
{
    boost::dynamic_bitset<> bs(5);
    cout << bs << endl;    // -> 00000
    bs.set(0);             // メンバ関数setで0ビット目を1にする
    cout << bs << endl;    // -> 00001
    bs.set(1).set(2);      // setやresetは*thisを返すので、メソッドチェーン形式で記述可能
    cout << bs << endl;    // -> 00111
    bs.set(2, false);      // setの第2引数にはboolを指定可能
    cout << bs << endl;    // -> 00011
    bs.set();              // 引数なしのsetは全てのビットを1にする
    cout << bs << endl;    // -> 11111
    bs.reset(0);           // メンバ関数resetで0ビット目を0にする
    cout << bs << endl;    // -> 11110
    bs.reset();            // 引数なしのresetは全てのビットを0にする
    cout << bs << endl;    // -> 00000
    bs[0] = true;          // []演算子で0ビット目を1にする
    cout << bs << endl;    // -> 00001
}

1の数を数える

メンバ関数count()を使う

#include <boost/dynamic_bitset.hpp>
#include <cassert>

int main()
{
    boost::dynamic_bitset<> bs(3); // -> 000
    assert(bs.count() == 0);
    bs.set();    // -> 111
    assert(bs.count() == 3);
}

ビットの値を検査する

特定のビットが1かを調べるにはメンバ関数test()もしくは[ ]演算子を使う。

1のビットがあるかどうかを調べるにはメンバ関数any(), none()を使う。

すべてのビットが1かどうかを調べるにはメンバ関数count()とsize()を組み合わせて使う。

#include <boost/dynamic_bitset.hpp>
#include <cassert>
#include <iostream>
using namespace std;

int main()
{
    // すべてのビットが0か調べる
    boost::dynamic_bitset<> bs(3);  // -> 000
    assert(bs.none());     

    // 特定のビットが1か調べる
    bs[0] = true;   // -> 001
    assert(bs[0]);
    assert(bs.test(0));

    // 1のビットがあるか調べる
    assert(bs.any());

    // すべてのビットが1か調べる    
    bs.set();  // -> 111
    assert(bs.count() == bs.size());   
}

文字列との相互変換

boost::dynamic_bitsetクラスでは演算子<<および>>がオーバーロードされているため、istream/ostreamを通して文字列との相互変換が可能である。

文字列からビット集合への変換は、コンストラクタに文字列を渡すことでも生成できる。

ビット集合から文字列への変換は、boost::to_string()関数を使用することもできる。

文字列は'0'か'1'のみから構成される必要があり、文字列の右端がインデックス0に対応することに注意。

#include <boost/dynamic_bitset.hpp>
#include <boost/lexical_cast.hpp>

int main()
{
    using boost::dynamic_bitset;
    using boost::lexical_cast;

    // std::string → dynamic_bitset
    dynamic_bitset<> bs(std::string("01"));  // コンストラクタに文字列を渡す
    assert(bs[0]);
    assert(!bs[1]);
    // dynamic_bitset → std::stirng
    std::string str;
    boost::to_string(bs, str);  // to_string 関数による変換

    // 演算子<<, >> がオーバーロードされているため、boost::lexical_castによる変換も出来る
    dynamic_bitset<> bs2 = lexical_cast<dynamic_bitset<> >("01");
    std::string str2 = lexical_cast<std::string>(bs2);
}

ビットの値を反転する

メンバ関数flip()でビットの値を反転できる。

#include <boost/dynamic_bitset.hpp>
#include <iostream>
using namespace std;

int main()
{
    boost::dynamic_bitset<> bs(3);
    cout << bs << endl;    // -> 000
    bs.flip(0);            // メンバ関数flipで0ビット目を反転
    cout << bs << endl;    // -> 001
    bs.flip();             // 引数なしのflipは全てのビットを反転させる
    cout << bs << endl;    // -> 110
}

集合演算

各種演算子(&, |, ^, ~,　-)およびその代入版(&=, |=, ^=, -=)によるビット毎の論理演算により、集合演算ができる。

ただし、2項演算子の引数のサイズは等しくなければならない。

#include <boost/dynamic_bitset.hpp>

int main()
{
    boost::dynamic_bitset<> bs1(4), bs2(4);
    bs1.set(0).set(1);    // -> 0011
    bs2.set(0).set(2);    // -> 0101

    ~bs1;        // -> 1100    ビット毎の否定 = 補集合
    bs1 & bs2;   // -> 0001    ビット毎の論理積 = 積集合
    bs1 | bs2;   // -> 0111    ビット毎の論理和 = 和集合
    bs1 ^ bs2;   // -> 0110    ビット毎の排他的論理和 = 対称差
    bs1 - bs2;   // -> 0010    差集合
}

2つの集合の包含関係を調べる

ビット集合A, Bがある時、AがBの部分集合（A ⊆ B)かを調べるには、メンバ関数is_subset_of()を使う。

同様に、AがBの真部分集合（A ⊂ B）かを調べるには、メンバ関数is_proper_subset_ofを、AとBが交差する（すなわち、AとBの積集合が空集合でない）かを調べるには、メンバ関数intersects()をそれぞれ使う。

#include <boost/dynamic_bitset.hpp>
#include <cassert>

int main()
{

    boost::dynamic_bitset<> A(4), B(4), C(4);
    A.set(0);           // -> 0001
    B.set(0).set(1);    // -> 0011
    C.set(2).set(3);    // -> 1100

    assert(A.is_subset_of(A));  // AはA自身の部分集合
    assert(!A.is_proper_subset_of(A));   // AはA自身の真部分集合ではない
    assert(A.is_proper_subset_of(B));    // AはBの真部分集合
    assert(A.intersects(B));    // AはBと交差する
    assert(!B.intersects(C));   // BはCと交差しない    
}

1が立っているインデックスを走査する

メンバ関数find_first()とfind_next()を組み合わせて、1が立っているインデックスを走査できる。 

#include <boost/dynamic_bitset.hpp>
#include <iostream>

int main()
{
    boost::dynamic_bitset<> bs(100);
    bs.set(10).set(20);

    // 1の立っているインデックスを走査
    for(boost::dynamic_bitset<>::size_type pos = bs.find_first();
        pos != bs.npos;
        pos = bs.find_next(pos))
    {
        std::cout << pos << std::endl;
    }
}

出力：

10
20

データサイズをカスタマイズする

boost::dynamic_bitsetは、第1テンプレート引数のBlock型のstd::vectorでビット列を管理する。

Blockのデフォルト値はunsigned longであるが、別の型を指定することでデータサイズをカスタマイズできる。

ただし、Blockは符号なし整数型でなければならない。

#include <boost/dynamic_bitset.hpp>
#include <cassert>

using boost::dynamic_bitset;

// デフォルトはunsigned long
static_assert(dynamic_bitset<>::bits_per_block == sizeof(unsigned long)*8, "");
// unsigned shortに変更
static_assert(dynamic_bitset<unsigned short>::bits_per_block == sizeof(unsigned short)*8, "");