さらにもっとビットと戯れる方法 - ESM アジャイル事業部開発者ブログ

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

三たび、RISC-Vシミュレータの作り方〜紅玉と錆と霊薬と〜 - ESM アジャイル事業部開発者ブログ

しかし残念ながら、誰もがいつでも 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
}