先頭へ戻る

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

Programming Place Plus トップページ -- C言語編 -- 逆引き

先頭へ戻る

この章の概要

この章の概要です。

目的

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

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

unsigned にしていますが、ビット演算(用語集)を行うときには、符号無し整数型を使うのが無難だからです(第49章

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

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

unsigned int bitArray[1000];

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

unsigned char bitArray[1000];

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

方法①(自力で実装する)

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

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

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

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

#include <limits.h>

unsigned char bitArray[(必要なビット数 + 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(bitNum)    (((bitNum) + CHAR_BIT - 1) / CHAR_BIT)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


void PrintBitArray(const unsigned char* bitArray, unsigned int bitMum)
{
    for (unsigned int i = bitMum; i > 0; --i) {
        if (bitArray[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 bitArray[BIT_ARRAY_SIZE(BIT_NUM)] = {0};  // すべて 0 で初期化

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


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


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

    return 0;
}

実行結果:

0000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000110
0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010111
0101010101010101010101010101010101010101010101010101010101010101010101000000000000000000000000000000

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

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

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

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

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

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

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

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



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

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

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


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


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

    return 0;
}

実行結果:

0000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000110
0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010111
0101010101010101010101010101010101010101010101010101010101010101010101000000000000000000000000000000

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

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

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


参考リンク


更新履歴



逆引きのトップページへ

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

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー