C++でビット配列（Bit Array）を実装する方法｜ビット操作のサンプルコード付き

これは、ビット配列（Bit Array）をC++で実装するプログラムの解説です。ビット配列とは、データを1ビット単位でコンパクトに格納できる配列データ構造の一種で、シンプルなデータ構造を実装するために広く利用されます。各要素が0か1の値のみを保持するため、通常の整数型配列と比べてメモリを大幅に節約できる点が大きな特徴です。

アルゴリズム

使用する関数と擬似コード：

Begin
    Function getBit(int val,int pos)  // valのpos番目のビットを取得
    singleBit->b = 0
    if(pos == 0)
        singleBit->b = val & 1
    else
        singleBit->b = ( val & (1 << pos ) ) >> pos
        return singleBit
    Function setBit(BitArr *bt,B *bit,int pos)  // pos番目の位置にビットを設定
        bt->bVal[pos] = bit
        return bt
    Function getVal(BitArr *bArray)  // ビット配列から整数値を復元
    initialize val = 0
    initialize bVal = 0
    bVal = bArray->bVal[0]->b
    val= val|bVal
    for i = 1 to B_A_LENGTH-1
        bVal = bArray->bVal[i]->b
        bVal =bVal << i
        val=val | bVal
        return val
    done
End.

各関数の役割

getBit関数： 整数値valのpos番目のビットを取り出します。posが0の場合は「val & 1」で最下位ビットを取得し、それ以外の場合は「(val & (1 << pos)) >> pos」で該当位置のビットを抽出します。

setBit関数： 取得したビットを、ビット配列オブジェクトの指定した位置posに格納します。

getVal関数： ビット配列に格納された各ビットを元のビット位置へシフトし、論理和（OR）を順に適用することで、元の整数値を復元します。

サンプルコード

#include <iostream>
#include <string>
using namespace std;
#define B_A_LENGTH 4
typedef struct {
    unsigned int b : 1;
} B;
class BitArr {
    private:
    B **bVal;
    public:
    BitArr() {
        bVal = new B* [B_A_LENGTH];
    }
    B *getBit(int val,int pos) {
        B *singleBit = new B;
        singleBit->b = 0;
        if(pos == 0) {
            singleBit->b = val & 1;
        } else {
            singleBit->b = ( val & (1 << pos ) ) >> pos;
        }
        return singleBit;
    }
    BitArr *setBit(BitArr *bt,B *bit,int pos) {
        bt->bVal[pos] = bit;
        return bt;
    }
    int getVal(BitArr *bArray) {
        int val = 0;
        unsigned int bVal = 0;
        bVal = bArray->bVal[0]->b;
        val |= bVal;
        for(int i = 1; i < B_A_LENGTH; i++) {
            bVal = bArray->bVal[i]->b;
            bVal <<= i;
            val |= bVal;
        }
        return val;
    }
};
int main() {
    int v;
    cout<<"Enter 4 bit integer value (0 - 8): ";
    cin>>v;
    BitArr bt, *samplebt;
    samplebt = new BitArr;
    for (int i = 0; i < B_A_LENGTH; i++) {
        samplebt = bt.setBit(samplebt, bt.getBit(v, i), i);
        cout<<"Bit of "<<v<<" at positon "<<i<<": "<<"\n"<<bt.getBit(v, i)->b<<endl;
    }
    cout<<"The value is: "<<bt.getVal(samplebt)<<endl;
    return 0;
}

実行結果

Enter 4 bit integer value (0 - 8): 6
Bit of 6 at positon 0:
0
Bit of 6 at positon 1:
1
Bit of 6 at positon 2:
1
Bit of 6 at positon 3:
0
The value is: 6

このプログラムでは、4ビットの整数値を入力すると、各ビット位置（0〜3）の値を順に表示し、最後にビット配列から復元した値を出力します。入力例の「6」は2進数で「0110」を表すため、ビット位置0から順に「0、1、1、0」と表示され、復元された値も元どおり「6」になります。このようにビット配列を利用すると、個々のビットを独立に操作しながら、必要に応じて元の整数値を簡単に再構成できます。