C++-এ বিট অ্যারে (Bit Array) বাস্তবায়ন

বিট অ্যারে (Bit Array) একটি অ্যারে ডেটা স্ট্রাকচার যা ডেটা খুব কমপ্যাক্টলি (compactly) সংরক্ষণ করে। প্রতিটি বিট একটি বুলিয়ান ভ্যালু (০ বা ১) রিপ্রেজেন্ট করে। এটি স্পেস-এফিশিয়েন্ট সিম্পল ডেটা স্ট্রাকচার বাস্তবায়নে ব্যবহৃত হয়।

এলগরিদম ও পসিউডোকোড

শুরু
  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
শেষ

উদাহরণ কোড

#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 - 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>, std::vector<bool> বা বাইট অ্যারে + বিটওয়াইজ অপারেশন ব্যবহার করা উচিত। বিট-ফিল্ড (unsigned int b : 1) কম্পাইলার-নির্ভর প্যাডিং দিয়ে মেমরি বাঁচাতে পারে না।