비트맵 (Bitmap)

비트맵 (Bitmap)

각 비트를 하나의 플래그 또는 상태로 사용하는 공간 효율적인 집합 표현 방식으로, 비트 연산을 통해 원소의 존재 여부를 빠르게 판단

목적: 공간 효율, 빠른 집합 연산, 플래그 관리, 메모리 최소화

특징: 비트 단위 저장, 비트 연산, 매우 작은 메모리, O(1) 접근

구성요소: 정수 배열 또는 비트 배열, 비트 연산(AND: 교집합, OR: 합집합, XOR: 대칭차집합, NOT: 여집합, SHIFT: 비트 이동)

연산

• •set(i): bitmap[i/32] |= (1 << (i%32)) - i번째 비트 1로 설정, O(1)
• •clear(i): bitmap[i/32] &= ~(1 << (i%32)) - i번째 비트 0으로, O(1)
• •test(i): bitmap[i/32] & (1 << (i%32)) - i번째 비트 확인, O(1)
• •flip(i): bitmap[i/32] ^= (1 << (i%32)) - i번째 비트 반전, O(1)

시간 복잡도: 모든 비트 연산 O(1)

공간 복잡도: O(n/8) 바이트 - 일반 배열의 1/8

장점: 매우 작은 메모리, 빠른 연산(O(1)), 비트 연산 효율, 캐시 효율

단점: 희소 집합에서 비효율, 순회 느림(O(n)), 크기 제한(미리 결정)

적용사례: 소수 판정(에라토스테네스의 체), 권한 플래그, 자원 할당, 네트워크 라우팅 테이블, 블룸 필터

비교: 비트맵(밀집/빠름/작음) vs 해시 셋(희소/유연/큼)

연관: 비트 연산, 집합, 에라토스테네스의 체, 블룸 필터