Bit vector (비트벡터)

Bit Vector

$0 \le i \le N$ 이라 하자.

i번째 원소에 1 을 저장하거나 이미 1인지 검사하는 문제를 생각해봅시다.

int *A = new int[N](); // 0으로 초기화  

if(A[i]==1)
    printf("이미 1")
else
    A[i] = 1

int가 4 byte이므로 총 4N byte가 필요할 것입니다.

공간을 줄일려면 크기가 N인 bool 배열을 생성하면 됩니다.

bool *A = new bool[N]();  // false로 초기화
A[i] = True;

bool은 크기가 1byte만 가지므로 총 N byte가 필요합니다.

하지만 크기를 더 줄일 수 있는데요, 1, 0 두 개만 저장하면 되므로 1byte가 아니라 1bit가 필요합니다.

int는 대부분의 컴파일러에서 4byte로 제공하고 있고.

4 byte 는 32bit 입니다.

따라서 int 1개당 32개의 원소에 대한 정보를 저장할 수 있습니다.

주어진 i를 정수 n의 k 번째 bit에 위치하는지 알아내면 됩니다.

i	n
0~31	0
32~63	1
64~95	2

n은 쉽게 구할 수 있습니다.

$n =\lfloor i/32 \rfloor$

또는

$n =$ $i$>>$5$

n을 구했다면 정수 n 의 몇 번째 bit 인지 구하면 됩니다.

k도 쉽게 구할 수 있습니다.

$k = i \% 32$

또는

$k = i$ & 0X1f

Ex) $i = 35$ 는 정수 1의 3번째 bit.

n = 1

k = 3

Code

int *A = new int[N/32](); // 한 int 당 32개의 정보 저장 가능

if (A[i>>5] & 1>>(i & 0x1f)) // 0이 첫 번째 비트에 저장되므로 1칸을 옮겨줘야 합니다.
    printf("이미 1")
else
    A[i>>5] |= 1>>(i & 0x1f)

Apply

해싱을 이용할 때의 응용?

예제) 문자열이 주어졌을 때 중복되는 문자가 있는지 판별하라.