ESM アジャイル事業部 開発者ブログ

永和システムマネジメント アジャイル事業部の開発者ブログです。

さらにもっとビットと戯れる方法

前回は「Elixir はビット列操作が得意」という話をした e.mattsan です。

しかし残念ながら、誰もがいつでも Elixir を使えるとは限りません。

Elixir は使えないけれど、ビットと戯れたい。 それならば、自分が使う言語で戯れるしくみを自分で作ればいいじゃないか。 自分が得意とする言語を、自分でビット操作を得意なものにしてしまえばいい。

今回は、そんな話です。

ここではわたしが一番長く使ってきた C++ を使いますが、みなさんは、自分が得意とする言語ならどう書くか、想像しながら読んでみてください。 また、ここでのコードは C++11 までの仕様しか利用していないので、それほど難しくはないと思います。 たぶん。

なお。 本格的なライブラリを作成するのは、この記事1つでは手にあまるので、扱えるビット列は unsigned int のサイズまで、という制限付きとさせてもらいました。

今回の記事で書いたコードは GitHub Gist でも公開しています。興味のある方は参照してみてください。

第一段階、指定した長さのビット列を格納する

ビット列を格納するだけであれば、組み込みの整数型でも充分で、新しく型を定義するまでもありません。 ですがビット列にはビット長も大切な情報です。 そこで数値とビット長を指定できるビット列クラスを最初に定義します。

通常の整数値と互いに代入や変換ができるように、代入演算子 operator = (unsigned int) と、型変換演算子 operator unsigned int () const も定義しました。

template<unsigned int N> class Bits {
public:
    typedef Bits<N> TYPE;
    static const unsigned int SIZE = N;
    static const unsigned int MASK = (1u << SIZE) - 1u;

    Bits(unsigned int value) : value_(value & MASK) {}

    // unsigned int の値を代入できるようにするための代入演算子
    TYPE& operator = (unsigned int new_value) {
        value_ = new_value & MASK;
        return *this;
    }

    // unsigned int に変換できるようにするための型変換演算子
    operator unsigned int () const { return value_; }
private:
    unsigned int value_;
};

定義した型を使ってみます。

ビット長はテンプレート引数で指定します。 指定したビット長に収まるビット列であれば普通の符号なし整数の値のようにふるまいますが、ビット長を超える値を代入すると超えた部分は捨てられてしまいます。

#include <iostream>

using namespace std;

int main(int, char* []) {
    Bits<3> a(0x02); //       010
    Bits<5> b(0x03); //    0_0011
    Bits<8> c(0x04); // 0000_0100

    cout << hex;

    cout << "a = " << a << "\n"  // => 2
         << "b = " << b << "\n"  // => 3
         << "c = " << c << "\n"; // => 4

    // 格納できるビット長より大きな値を代入する
    a = 0x09;  //        1001
    b = 0x21;  //     10_0001
    c = 0x101; // 1_0000_0001

    cout << "a = " << a << "\n"  // => 1
         << "b = " << b << "\n"  // => 1
         << "c = " << c << "\n"; // => 1
}

ビット長を持つクラスを定義できたので、次に「3ビットの値と5ビットの値を連結して8ビットの値を作る」ということをやってみます。

第二段階、ビット列を結合する

今回は連結したビット列を表す Composit を導入します。

今回も型変換演算子 operator unsigned int () const を用意したので、符号なし整数値として参照することができますが、内部では整数値でなく2つのビット列を格納しています。

符号なし整数値として参照すると、ビット列をシフトして連結し、1つの符号なし整数値として返却します。

template<unsigned int N, unsigned int M> class Composit {
public:
    typedef Composit<N, M> TYPE;
    typedef Bits<N> LEFT_TYPE;
    typedef Bits<M> RIGHT_TYPE;
    static const unsigned int SIZE = LEFT_TYPE::SIZE + RIGHT_TYPE::SIZE;
    static const unsigned int MASK = (1u << SIZE) - 1u;

    Composit(LEFT_TYPE& left, RIGHT_TYPE& right) : left_(left), right_(right) {}

    // 型変換演算子
    operator unsigned int () const {
        return ((static_cast<unsigned int>(left_) << RIGHT_TYPE::SIZE) | static_cast<unsigned int>(right_)) & MASK;
    }

private:
    LEFT_TYPE& left_;
    RIGHT_TYPE& right_;
};

このままだと Composit を使うたびに2つのテンプレート引数をそのつど指定しなければなりませんので、それを簡単にするためにヘルパ関数テンプレートを用意します。 引数の型から自動的に必要な値が取得できるので、テンプレート引数を書く手間がはぶけます。

template<unsigned int N, unsigned int M> Composit<N, M> combine(Bits<N>& left, Bits<M>& right) {
    return Composit<N, M>(left, right);
}

定義した型を使ってみます。

#include <iostream>

using namespace std;

int main(int, char* []) {
    Bits<3> a(0x02); //    010
    Bits<5> b(0x03); // 0_0011

    cout << hex;

    cout << "a = " << a << "\n"               // =>       010 = 0x02
         << "b = " << b << "\n"               // =>    0_0011 = 0x03
         << "ab = " << combine(a, b) << "\n"  // => 0100_0011 = 0x43
         << "ba = " << combine(b, a) << "\n"  // => 0001_1010 = 0x1a
         << "aa = " << combine(a, a) << "\n"; // =>   01_0010 = 0x12
}

Bits の型変換演算子は格納している数値を返すだけでしたが、Composit の型変換演算子は格納している Bits<N>Bit<M> の値を連結する処理をしています。

これによって数値を取り出すために unsigned int に変換されるときに、2つの値を連結して1つの数値として返すことができます。

  • combine(a, b)

  • combine(b, a)

  • combine(a, a)

第三段階、ビット列に代入する

さらに、連結した状態のビット列に数値を代入することで、格納しているビット列に代入された数値の一部分をそれぞれ格納できるようにします。 ビット列を連結して数値に変換するときと逆の処理です

第二段階で作成した Composit に、代入演算子 operator = (unsigned int) を定義します。

ここでメンバ変数を参照で定義したことが効いてきます。 参照で定義したので、メンバ変数は元のビット列そのものを指し示しているため、メンバ変数へ代入すると元のビット列へ代入したのと同じ結果が得られます。

template<unsigned int N, unsigned int M> class Composit {
public:
    // 第二段階と同じなので省略

    // 代入演算子
    TYPE& operator = (unsigned int new_value) {
        left_ = (new_value >> RIGHT_TYPE::SIZE) & LEFT_TYPE::MASK;
        right_ = new_value & RIGHT_TYPE::MASK;
        return *this;
    }

    // 第二段階と同じなので省略
};

代入してみます。

#include <iostream>

using namespace std;

int main(int, char* []) {
    Bits<3> a(0);
    Bits<5> b(0);

    combine(a, b) = 0x3c; // 0011_1100 => 001, 1_1100 = 0x01, 0x1c

    cout << hex
         << "a = " << a << "\n"  // => 0x01
         << "b = " << b << "\n"; // => 0x1c

    combine(a, b) = combine(b, a); // 1_1100, 001 -> 1110_0001 -> 111, 0_0001 = 0x07, 0x01

    cout << hex
         << "a = " << a << "\n"  // => 0x07
         << "b = " << b << "\n"; // => 0x01
}
  • combine(a, b) = 0x3c

  • combine(a, b) = combine(b, a)

これは元のビット列の上位と下位を入れ替える操作になっています。

2つのビット列を格納する Composit<N, M> のオブジェクトを生成し、それを整数値に変換し、その値を Composit<M, N> のオブジェクトに代入することで、元のそれぞれのビット列に数値の一部分ずつが代入されます。

第四段階、コンマ演算子オーバーロード

combine(a, b) = combine(b, a) という、関数の戻り値に値を代入する式は、見慣れないと奇異に感じるかもしれません。 Ruby のように多重代入が可能な言語を使っている方でしたら、せめて (a, b) = (b, a) みたいに書ければよいのに、と感じるかもしれません。

実は C++ でも不可能ではありません。 コンマ演算子を使えば、そんな書き方も可能です。

C++ は多くの演算子の多重定義が可能ですが、コンマ演算子( operator , )も定義できてしまいます。 コンマ演算子に関数 combine<N, M>(Bits<N>&, Bits<M>&) と同じ機能を持たせれば、(a, b) と書くだけで combine(a, b) と同じ結果がえられるようになるはずです。

ここでは単純に内部で combine(a, b) を呼び出すだけの、関数の別名として定義します。

template<unsigned int N, unsigned int M> Composit<N, M> operator , (Bits<N>& left, Bits<M>& right) {
    return combine(left, right);
}

combine(a, b)combine(b, a)(a, b)(b, a) に書き換えます。

#include <iostream>

using namespace std;

int main(int, char* []) {
    Bits<3> a(0);
    Bits<5> b(0);

    (a, b) = 0x3c; // 0011_1100 => 001, 1_1100 = 0x01, 0x1c

    cout << hex
         << "a = " << a << "\n"  // => 0x01
         << "b = " << b << "\n"; // => 0x1c

    (a, b) = (b, a); // 1_1100, 001 -> 1110_0001 -> 111, 0_0001 = 0x07, 0x01

    cout << hex
         << "a = " << a << "\n"  // => 0x07
         << "b = " << b << "\n"; // => 0x01
}

これで、ビット長を指定したビット列の変数の定義と代入だけで、ビット列を分割したり連結したりできる…ような見栄えになりました。

第五段階、三つ以上の値を扱う

もっと複数のビット列を連結したい場合はさらに工夫が必要です。

Composit<N, M>Bit<N>Bit<M> の2つしか格納できません。

3つのビット列を格納する Composit<N, M, L> を定義するのもの一つの考えです。 例えば最大で16ビットまで扱わないのであれば、引数が2から16までのテンプレートを用意することでまかなえます。

それよりも再起的な構造にする方が自然な考えかもしれません。 コンマ演算子は左から結合するので (a, b, c)((a, b), c) と同じ意味になります。 つまり、次の図のような構造があつかえれば再起的に3つ以上の連結をあつかえるようになるはずです。

ただし、C++は静的型付けの言語なので、これを実現するための工夫が必要です。

その工夫もまた興味深い話題になるのですが、ビット列操作を離れてデータ構造の世界に突入してしまうので、今回はこれまでにしたいと思います。

第六段階、あなたのプログラミング言語で実装する

ここまでC++でビット列の操作をどこまであつかいやすくできるかを見てきました。 C++を選んだのは、最初に書いたとおり、わたしが長く使ってきて手に馴染んでいるからでです。 そしてC++のテンプレートや演算子の多重定義というしくみを利用して戯れてみました。

みなさんにはみなさんの手に馴染んでいる言語があると思います。 その言語ではC++とはまた違ったスタイルになるでしょう。 もっと効果的で明快で楽しくビット列操作を達成できる方法がおそらくあると思います。

もし「これは」というコードができましたら、 https://twitter.com/emattsan などで反応いただけたらと思います。


そして、もし、それを仕事にしてみたいと思ったら、日々こんなことを考えているプログラマがいるところに、応募してみるのも面白いかもしれません。

株式会社永和システムマネジメントアジャイル事業部はエンジニアを絶賛募集しています。

プログラミング好きの方のエントリをお待ちしております。

agile.esm.co.jp