C++로 비트 배열(Bit Array) 구현하기: 알고리즘과 예제 코드

이 글에서는 C++를 사용하여 비트 배열(Bit Array)을 구현하는 방법을 알아봅니다. 비트 배열은 데이터를 비트 단위로 압축적으로 저장하는 배열 기반 자료구조로, 메모리 효율성이 중요한 간단한 자료구조를 만들 때 널리 활용됩니다.

비트 배열이란?

비트 배열은 각 요소가 0 또는 1의 값만 가질 수 있는 배열입니다. 일반적인 int 배열이 숫자 하나에 4바이트(32비트)를 사용하는 반면, 비트 배열은 비트 필드(bit-field)를 활용해 각 요소를 1비트로 저장할 수 있어 메모리를 크게 절약할 수 있습니다.

알고리즘

이 프로그램은 세 가지 핵심 함수로 구성됩니다.

getBit(val, pos): 정수 값에서 특정 위치의 비트를 추출합니다.
setBit(bt, bit, pos): 추출한 비트를 배열의 해당 위치에 저장합니다.
getVal(bArray): 비트 배열에 저장된 비트들을 다시 하나의 정수 값으로 조합합니다.

의사코드:

Begin
    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)
        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.

핵심 동작 원리

비트 추출에는 비트 마스킹과 시프트 연산이 사용됩니다. (val & (1 << pos)) >> pos 연산은 원하는 위치의 비트만 남긴 뒤 오른쪽으로 밀어내어 0 또는 1의 값을 얻습니다. 반대로 값을 재조합할 때는 각 비트를 해당 위치만큼 왼쪽으로 시프트한 후 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<<": "<<"
"<<bt.getBit(v, i)->b<<endl;
    }
    cout<<"The value is: "<<bt.getVal(samplebt)<<endl;
    return 0;
}

코드 구조 살펴보기

먼저 typedef struct { unsigned int b : 1; } B;로 1비트 크기의 비트 필드를 정의합니다. 이후 BitArr 클래스가 비트 포인터들의 배열을 관리하며, 입력받은 정수의 각 비트를 추출해 저장하고, 다시 원래 값으로 복원하는 전체 과정을 수행합니다.

실행 결과

값 6(이진수 0110)을 입력했을 때의 출력 결과입니다.

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

각 위치의 비트가 올바르게 추출되었으며, 저장된 비트들을 다시 조합했을 때 원래 입력 값인 6이 그대로 복원되는 것을 확인할 수 있습니다. 이처럼 비트 배열은 비트 단위 연산만으로 데이터를 저장하고 복원할 수 있는 효율적인 자료구조입니다.