โปรแกรม C++ สำหรับการใช้งาน Bit Array

Bit Array เป็นโครงสร้างข้อมูลอาร์เรย์ที่จัดเก็บข้อมูลอย่างกระชับ (compact) ใช้สำหรับการใช้งานโครงสร้างข้อมูลแบบง่ายๆ โดยแต่ละบิตแทนค่า 0 หรือ 1

อัลกอริธึมและ Pseudocode

Function getBit(int val, int 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):
    bt.bVal[pos] = bit
    return bt

Function getVal(BitArr *bArray):
    val = 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
End

โค้ดตัวอย่าง

#include <iostream>
#include <string>
using namespace std;

#define B_A_LENGTH 4

typedef struct {
    unsigned int b : 1; // bit field: 1 บิต
} B;

class BitArr {
private:
    B **bVal; // อาร์เรย์ของ pointer ไปยัง B

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 - 15): ";
    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 position " << i << ": " << bt.getBit(v, i)->b << endl;
    }
    cout << "The value is: " << bt.getVal(samplebt) << endl;
    return 0;
}

ผลลัพธ์

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

วิธีทันสมัย (แนะนำ): ใช้ std::bitset<N> (fixed size) หรือ std::vector<bool> / boost::dynamic_bitset (dynamic size) ซึ่งมี API ครบครัน ประหยัดหน่วยความจำ และทดสอบ済แล้ว

#include <bitset>
#include <iostream>
using namespace std;
int main() {
    bitset<4> b(6); // 0110
    cout << b << endl;        // 0110
    cout << b[1] << endl;     // 1 (LSB = index 0)
    b.flip();                // 1001
    cout << b.to_ulong() << endl; // 9
}