ビット単位の配列 | Programming Place Plus　Ｃ言語編　逆引き

トップページ – Ｃ言語編 – 逆引き

このページの概要 🔗

このページの解説は C99 をベースとしています。

以下は目次です。

目的 🔗

1ビット単位でデータを取り扱う配列を実現したいとします。

10ビットだとか、30ビットだとかという程度であれば、unsigned int型の変数を１つ用意して、32ビット分のビット列として扱うことができます（unsigned int型が 32ビットであるという想定）。

unsigned にしていますが、ビット演算を行うときには、符号無し整数型を使うのが無難だからです（第４９章）

しかし、1000ビットとか 2000ビットとかいうような長いビット列が必要な場合、単独の変数では実現できません。

変数の個数を増やせば実現できそうなので、配列を使うことを考えますが、1000ビット欲しいからといって、

unsigned int bit_array[1000];

のように書いたら無駄が大きすぎます。Ｃ言語に存在する一番小さい型は char型ですが、それでも最低 8ビットの大きさを持つので、

unsigned char bit_array[1000];

これでも全体で 8000ビットあることになり、相当に無駄になっています。この無駄を減らす方法を取り上げます。

方法①（自力で実装する） 🔗

まず、Ｃ言語にはビット単位の配列を表現する直接的な方法はありません。冒頭でみたような感じで、unsigned char型などで配列を作り、あとは何とかうまくやるしかありません。

まず、確保する大きさの無駄をぎりぎりまで減らします。

unsigned char型の大きさは最低 8ビットです。現実的にもほぼ 8ビットで間違いないですが、正確には CHAR_BITの置換結果を見なければなりません。CHAR_BIT は limits.h にあります。

これを踏まえると、次のように配列を宣言すれば無駄を減らせます。

#include <limits.h>

unsigned char bit_array[(必要なビット数 + CHAR_BIT - 1) / CHAR_BIT];

必要なビット数が 1000、CHAR_BIT が 8 とすると、(1000 + 8 - 1) / 8 なので、この配列の要素数は 125 です。CHAR_BIT が 8 なら unsigned char型は 8ビットですから、「125 * 8」で 1000ビット確保されていることになります。

必要なビット数が 1 だとすると、(1 + 8 - 1) / 8 なので、要素数 1 で確保されます。これは 8ビット確保されているということですから、7ビット分は無駄になっていますが、これが切り詰められる限界のラインです。

ところで、この宣言はちょっと鬱陶しいので、マクロでごまかすのも手です。

#include <limits.h>
#define BIT_ARRAY_SIZE(bit_num)    (((bit_num) + CHAR_BIT - 1) / CHAR_BIT)

unsigned char bit_array[BIT_ARRAY_SIZE(必要なビット数)];

こうしてビット配列そのものは作ることができますが、目的のビットがどこにあるのかを求めなければならず、ここでビット演算を活用する必要があります。

つまり、1000ビットのビット列を unsigned char bit_array[BIT_ARRAY_SIZE(1000)]; と宣言したとき、最下位から 50ビット目は、bit_array のどこにあるのか、ということです。１つの要素に 8ビット分の情報が詰め込まれているのですから、bit_array[50] ではありません。これは、目的のビット番号 / CHAR_BIT という計算によって算出できます。50ビット目なら 50 / 8 ということになり、bit_array[6] のところにあることが分かります。

この計算はよく使うので、インライン関数やマクロにしておくと便利です。

inline unsigned int BIT_ARRAY_INDEX(unsigned int bit_index)
{
    return bit_index / CHAR_BIT;
}

// インライン関数の方がいいが
// #define BIT_ARRAY_INDEX(bit_index) ((bit_index) / CHAR_BIT)

これで、50ビット目だけ 0 にするコードを次のように書けるでしょうか？

// 50ビット目だけ 0 にする？（正しくない）
bit_array[BIT_ARRAY_INDEX(50)] = 0;

これは間違っています。この代入が意味することは何でしょう？　BIT_ARRAY_INDEX を使って、50ビット目の位置を特定したものの、そこにあるのは１つの unsigned char型の変数です。そのため、0 を代入するこの文がしていることは、8ビットの 00000000 の代入です。

そこで今度は、50ビット目が bit_array[6] を構成している 8ビットの中のどのビットなのかを特定する必要があります。これは、目的のビット番号 % CHAR_BIT で算出できます。これまたインライン関数やマクロにすると、次のように書けます。

inline unsigned int BIT_ARRAY_BIT(unsigned int bit_index)
{
    return bit_index % CHAR_BIT;
}

// インライン関数の方がいいが
// #define BIT_ARRAY_BIT(bit_index)   ((bit_index) % CHAR_BIT)

// 50ビット目だけ 0 にする
bit_array[BIT_ARRAY_INDEX(50)] &= ~(1 << BIT_ARRAY_BIT(50));

特定のビットを 0 にするビット演算については、「逆引き　ビットを 0 にする」を参照してください。BIT_ARRAY_BIT で得られる結果は、指定のビットが１つの要素の中の何ビット目にあたるのかです。そのため、実際にその位置のビットを操作するには 1 << BIT_ARRAY_BIT(50) のようにシフト演算を加えなければなりません。

ここまでをまとめると、次のようにプログラムを作れます。

#include <limits.h>
#include <stdio.h>

/*
    ビット配列の要素数を計算する
    bit_num: 必要なビット数
*/
#define BIT_ARRAY_SIZE(bit_num)    (((bit_num) + CHAR_BIT - 1) / CHAR_BIT)

/*
    ビット配列の指定ビットが何番目の要素にあるか計算する
    bit_index: ビット配列の最下位から何ビット目か
*/
inline unsigned int BIT_ARRAY_INDEX(unsigned int bit_index)
{
    return bit_index / CHAR_BIT;
}

/*
    ビット配列の指定ビットが、要素内で何ビット目にあるか計算する
    bit_index: ビット配列の最下位から何ビット目か
*/
inline unsigned int BIT_ARRAY_BIT(unsigned int bit_index)
{
    return bit_index % CHAR_BIT;
}


void print_bit_array(const unsigned char* bit_array, unsigned int bit_num)
{
    for (unsigned int i = bit_num; i > 0; --i) {
        if (bit_array[BIT_ARRAY_INDEX(i-1)] & (1 << BIT_ARRAY_BIT(i-1))) {
            printf("1");
        }
        else {
            printf("0");
        }
    }
    printf("\n");
}

int main(void)
{
    #define BIT_NUM 100
    unsigned char bit_array[BIT_ARRAY_SIZE(BIT_NUM)] = {0};  // すべて 0 で初期化

    // 特定のビットを 1 にする
    bit_array[BIT_ARRAY_INDEX(1)] |= (1 << BIT_ARRAY_BIT(1));
    bit_array[BIT_ARRAY_INDEX(2)] |= (1 << BIT_ARRAY_BIT(2));
    bit_array[BIT_ARRAY_INDEX(50)] |= (1 << BIT_ARRAY_BIT(50));
    print_bit_array(bit_array, BIT_NUM);


    // 奇数ビットを 1 にする
    for (unsigned int i = 0; i < BIT_NUM; i += 2) {
        bit_array[BIT_ARRAY_INDEX(i)] |= (1 << BIT_ARRAY_BIT(i));
    }
    print_bit_array(bit_array, BIT_NUM);


    // 下位の 30ビット分を 0 にする
    for (unsigned int i = 0; i < 30; ++i) {
        bit_array[BIT_ARRAY_INDEX(i)] &= ~(1 << BIT_ARRAY_BIT(i));
    }
    print_bit_array(bit_array, BIT_NUM);
}

実行結果：

0000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000110
0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010111
0101010101010101010101010101010101010101010101010101010101010101010101000000000000000000000000000000

インライン関数を使って多少短くなっているとはいえ、ビット配列内のビットを操作するときの記述量が多く、間違いやすくもあるので注意が必要です。

そこでさらに、「ビットを書き込む」「ビットが 1 かどうか調べる」といったインライン関数を導入すれば、より楽になります。

#include <limits.h>
#include <stdbool.h>
#include <stdio.h>

/*
    ビット配列の要素数を計算する
    bit_num: 必要なビット数
*/
#define BIT_ARRAY_SIZE(bit_num)    (((bit_num) + CHAR_BIT - 1) / CHAR_BIT)

/*
    ビット配列の指定ビットが何番目の要素にあるか計算する
    bit_index: ビット配列の最下位から何ビット目か
*/
inline unsigned int BIT_ARRAY_INDEX(unsigned int bit_index)
{
    return bit_index / CHAR_BIT;
}

/*
    ビット配列の指定ビットが、要素内で何ビット目にあるか計算する
    bit_index: ビット配列の最下位から何ビット目か
*/
inline unsigned int BIT_ARRAY_BIT(unsigned int bit_index)
{
    return bit_index % CHAR_BIT;
}

/*
    ビット配列の指定ビットに 0 か 1 をセットする
    bit_array: ビット配列
    bit_index: ビット配列の最下位から何ビット目か
    v: 0 をセットするなら false、1 をセットするなら true
*/
inline void BIT_ARRAY_SET_BIT(unsigned char* bit_array, unsigned int bit_index, bool v)
{
    if (v) {
        bit_array[BIT_ARRAY_INDEX(bit_index)] |= (1 << BIT_ARRAY_BIT(bit_index));
    }
    else {
        bit_array[BIT_ARRAY_INDEX(bit_index)] &= ~(1 << BIT_ARRAY_BIT(bit_index));
    }
}

/*
    ビット配列の指定ビットの状態を返す
    bit_array: ビット配列
    bit_index: ビット配列の最下位から何ビット目か
    戻り値: 0 なら false、1 なら true を返す
*/
inline bool BIT_ARRAY_GET_BIT(const unsigned char* bit_array, unsigned int bit_index)
{
    return bit_array[BIT_ARRAY_INDEX(bit_index)] & (1 << BIT_ARRAY_BIT(bit_index));
}



void print_bit_array(const unsigned char* bit_array, unsigned int bit_num)
{
    for (unsigned int i = bit_num; i > 0; --i) {
        if (BIT_ARRAY_GET_BIT(bit_array, i - 1)) {
            printf("1");
        }
        else {
            printf("0");
        }
    }
    printf("\n");
}

int main(void)
{
    #define BIT_NUM 100
    unsigned char bit_array[BIT_ARRAY_SIZE(BIT_NUM)] = {0};  // すべて 0 で初期化

    // 特定のビットを 1 にする
    BIT_ARRAY_SET_BIT(bit_array, 1, true);
    BIT_ARRAY_SET_BIT(bit_array, 2, true);
    BIT_ARRAY_SET_BIT(bit_array, 50, true);
    print_bit_array(bit_array, BIT_NUM);


    // 奇数ビットを 1 にする
    for (unsigned int i = 0; i < BIT_NUM; i += 2) {
        BIT_ARRAY_SET_BIT(bit_array, i, true);
    }
    print_bit_array(bit_array, BIT_NUM);


    // 下位の 30ビット分を 0 にする
    for (unsigned int i = 0; i < 30; ++i) {
        BIT_ARRAY_SET_BIT(bit_array, i, false);
    }
    print_bit_array(bit_array, BIT_NUM);
}

実行結果：

0000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000110
0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010111
0101010101010101010101010101010101010101010101010101010101010101010101000000000000000000000000000000

BIT_ARRAY_SET_BIT関数の実装では、分岐が必要になってしまうので、これが気になるなら、関数を分けます。

inline void BIT_ARRAY_SET_BIT(unsigned char* bit_array, unsigned int bit_index)
{
    bit_array[BIT_ARRAY_INDEX(bit_index)] |= (1 << BIT_ARRAY_BIT(bit_index));
}

inline void BIT_ARRAY_UNSET_BIT(unsigned char* bit_array, unsigned int bit_index)
{
    bit_array[BIT_ARRAY_INDEX(bit_index)] &= ~(1 << BIT_ARRAY_BIT(bit_index));
}


参考リンク 🔗


更新履歴 🔗


逆引きのトップページへ

Ｃ言語編のトップページへ

Programming Place Plus のトップページへ

はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポスト／フォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る