💡 Algorithm
[자바 코테 준비] 비트마스크 연산자, 집합 구현 정리
date
May 9, 2024
slug
java-coding-test-bitmask
author
status
Public
category
💡 Algorithm
tags
summary
비트마스킹을 통한 집합 구현 연산자 총정리
type
Post
thumbnail
구종만 <알고리즘 문제 해결 전략> 참고
비트 연산자
1. AND 연산 - 해당 비트가 켜져 있는지 확인
각 비트가 둘 다 켜져 있는 경우 1
int visited = a & (1 << k) // a의 k번째 비트가 켜져있는지 여부
2. OR 연산 - 해당 비트 켜기
각 비트가 둘 중 하나라도 켜져 있다면 1
a = a | (1 << k) // a의 k번째 비트 켜기
3. XOR 연산 - 해당 비트가 켜져 있으면 끄고, 꺼져 있으면 켠다
해당 비트가 둘 중 하나만 켜져 있는 경우 1, 그 외엔 0
a = a ^ (1 << k) // a의 k번째 비트가 켜져 있으면 끄고, 꺼져 있으면 켠다
4. NOT 연산 - 해당 값 반전
켜져 있는 비트는 끄고, 꺼져 있는 비트는 켠 결과를 반환
a = ~a
5. 시프트(shift) 연산
비트들을 왼쪽 또는 오른쪽으로 원하는 만큼 움직임, 빈자리는 0으로 채워짐
int c = a & b
비트 연산자 사용 시 주의할 점(특히 C에서)
1. C에서 비트 연산자들의 우선순위는 비교 연산자보다 낮다.
c = (6 & 4 == 4) 라고 한다면, 4 == 4가 먼저 계산되어 1(true)을 반환하고, 따라서 c에는 6 & 1의 값이 할당되게 된다. 따라서 비트 연산자를 이용할 때에는 항상 연산자마다 괄호를 씌워주는 것이 바람직하다.
2. 오버플로우(Overflow)를 조심하자.
2^50 을 구하기 위해서 1<<50 으로 표현한다면, C에서는 1은 32bit 상수 취급하기 때문에 50번 왼쪽으로 shift하게 되면 overflow가 발생하게 된다. 따라서 1LL로 표현을 해주어야 한다.
비트마스킹 집합 구현
"하나의 bit가 하나의 원소"
bit가 켜져 있으면 해당 원소가 집합에 포함되어 있다는 의미이고, 꺼져 있으면 포함되어 있지 않다는 의미이다.
따라서 N비트 정수 변수라면 N개의 원소를 갖는 집합의 부분집합들을 모두 표현할 수 있게 된다.
비트마스크를 이용하면 정수 하나로 표현이 가능하기 때문에 사용하는 메모리의 크기가 줄어든다.
연산 | 사용 예시 |
공집합 | A = 0 |
꽉 찬 집합 | A = (1 << 10) -1 |
원소 추가 | A |= (1 << k) |
원소 삭제 | A &= ~(1 << k) |
원소의 포함 여부 확인 | A & (1 << k) |
원소의 토글 | A ^= (1 << k) |
두 집합에 대해서 연산 | 합집합: A | B
교집합: A & B
차집합: A & (~B)
XOR집합: A ^ B |
집합의 크기 구하기 | Integer.bitCount(A) |
최소 원소 찾기 | int first = A & (-A)
(-A = ~A+1) |
최소 원소 지우기 | A &= (A - 1) |
모든 부분 집합 순회 | for(int subset = A; subset; subset = ((subset-1) & A)) { } |