Bit Array Class (Delphi)

전에 AniNames를 업데이트하면서 필요에 의해 작성해본 Class입니다.

개념은 간단합니다. 말 그대로 비트(bit)열을 배열처럼 다루게 해주는 클레스입니다.

예를들어 '00100101101011'의 비트열이 있다고 할때, 오른쪽에서 5번째 비트값을 조사하려고 하면 'BitArray.Items[4]' 와 같은 형식으로 참조할 수 있습니다. 특정 비트를 셋트할 때도 역시 마찬가지로 수행할 수 있습니다. (ex: BitArray.Items[n] := True)

그럼 이걸 어디에 써먹을 수 있을까요?

제 경우는 숫자의 중복을 검사하기 위해서 이 클레스를 활용했습니다. 가령, 0 ~ 999 중에서의 숫자들로 만들어진 수열이 있다고 할 때, 이 수열에서 중복된 수가 있는지 검사하려고 할때 Bit Array를 이용하면 간단하고 빠르게 처리할 수 있습니다.

우선 BitArray의 크기를 1000으로 잡고 생성합니다.

Numbers := TBitArray.Create(1000);

그러면 0 ~ 999까지를 인덱스로 활용할 수 있겠죠. 그러면 데이터로 숫자를 얽어들일 때마다 BitArray의 해당 인덱스를 참조(Numers.items[index])해서 그 비트를 1(True)로 셋트합니다. 만일 세트하려는 인덱스의 값이 이미 1로 셋트되어 있다면, 방금 읽어온 숫자는 중복된 수라는 의미가 됩니다.

그리고 이걸 좀더 응용하면 숫자를 정렬(Sort)할 때도 이용할 수 있습니다. 숫자를 읽어들이면서 해당 마찬가지로 해당 BitArray의 인덱스를 1로 셋트하고 난후, 반대로 BitArray를 순차적으로 읽어들여서 1로 셋트된 인덱스만 출력하면 그자체로 정렬이 수행되는 거죠. 알고리즘 속도는 O(2n). 출력하는 부분을 제외하면 O(n) 으로 Sort가 완료됩니다. 다만 이방법에는 숫자 사이에 중복이 없어야 한다는 전제조건이 붙습니다.

그리고 또 하나의 단점이라면 수의 범위가 클수록 메모리를 많이 차지하게 된다는 점입니다. 0~9999 까지의 수를 다루고자 한다면 1만개의 비트를 저장해야 합니다. 만일 그냥 보통의 배열(Array)을 가지고 수행한다면 4만 바이트(Integer Type), 40KB의 메모리가 필요합니다.

그런데 단 하나의 비트를 다루는데, 정수형(Integer Type)은 무려 4바이트의 공간을 쓰게 됩니다. 4바이트면 비트 32개를 다룰수 있는 크기인데, 이걸로 고작 비트 하나만 저장시킨다는건 낭비가 너무 심하죠. 그래서, 메모리를 좀더 효율적으로 활용해서 비트의 배열을 다루고자 하여 만든 것이 바로 이 BitArray 클레스가 되겠습니다.

이 BitArray는 기본적으로 정수(Integer)의 배열입니다. 다만 하나의 정수에 대한 4Byte 공간에 32개의 비트를 집어넣는 것이 핵심입니다. 즉 각 배열의 원소가 32개씩의 비트를 기억하도록 만은 것입니다.

여기서 n번째 비트의 값을 조사하기 위해서는,

Array[n div 32] shr (n mod 32) and 1
배열[n/32의 몫]의 값을 n/32의 나머지 만큼 오른쪽으로 쉬프트 시킴.
그리고 그 값과 정수 1을 비트 AND 연산을 시켜서 나온 값이 0 인지 1인지 판단.

그런데 n번째 비트에 값을 셋트할 때는 조금 신경을 써야하는데, 일단 1을 기록할 때와 0을 기록할 때, 각각 다른 방법을 사용해야 합니다.

(1) 1을 기록할 때:

Array[n div 32] := Array[n div 32] or (1 shl (n mod 32))
정수 1을 n/32의 나머지 만큼 왼쪽으로 쉬프트하고, 배열[n/32]의 값과 비트 OR 연산을 수행.

(2) 0을 기록할 때:

Array[n div 32] := Array[n div 32] and not (1 shl (n mod 32))
정수 1을 n/32의 나머지 만큼 왼쪽으로 쉬프트한 후에 비트를 반전(NOT 연산)시키고 나서, 배열[n/32]의 값과 비트 AND 연산을 수행.

이같은 원리에 의해서 작성한 클레스의 풀 소스는 다음과 같습니다.
(급조된 거다 보니 예외처리는 고려하지 않았습니다...)

unit Collection

interface

type
  TBitBlock = Word;

  TBitArray = class
  private
    FBitList: array of TBitBlock;
    FLength: Integer;
  protected
    function GetBitBlock(BlockIndex: Integer): TBitBlock;
    procedure SetBitBlock(BlockIndex: Integer; Value: TBitBlock);
    function GetItem(Index: Integer): Boolean;
    procedure SetItem(Index: Integer; Value: Boolean = True);
  public
    property Length: Integer read FLength;
    property Items[Index: Integer]: Boolean read GetItem write SetItem;

    constructor Create(Size: Integer);
    destructor Destroy; override;
    procedure Clear;
  end;

implementation

constructor TBitArray.Create(Size: Integer);
begin
  FLength := Size;
  SetLength(FBitList, Size div 32 + 1);
  Clear;
end;

destructor TBitArray.Destroy;
begin
  SetLength(FBitList, 0);
end;

function TBitArray.GetBitBlock(BlockIndex: Integer): TBitBlock;
begin
  Result := FBitList[BlockIndex];
end;

procedure TBitArray.SetBitBlock(BlockIndex: Integer; Value: TBitBlock);
begin
  FBitList[BlockIndex] := Value;
end;

function TBitArray.GetItem(Index: Integer): Boolean;
var
  block: TBitBlock;
begin
  block := GetBitBlock(Index div 32);
  Result := ((block shr (Index mod 32)) and 1) = 1;
end;

procedure TBitArray.SetItem(Index: Integer; Value: Boolean);
var
  block: TBitBlock;
  bit: Integer;
begin
  block := GetBitBlock(Index div 32);

  if Value then
    block := block or (1 shl (Index mod 32))
  else
    block := block and not(1 shl (Index mod 32));

  SetBitBlock(Index mod 32, block);
end;

procedure TBitArray.Clear;
var
  i: Integer;
begin
  for i := 0 to Length(FBitList)-1 do
    FBitList[i] := 0;
end;

end.

사용법:

BitArray := TBitArray.Create(1000); // 0 ~ 999까지의 인덱스를 가지는 비트 배열
BitArray.Items[777] := True; // 777번째 비트에 1을 기록.
BitArray.Items[776] := False; // 776번째 비트에 0을 기록.
BitArray.Clear; // 모든 비트열을 0으로 초기화