1. 비트마스크
비트(bit)연산을 사용해 부분집합을 표현할 수 있는 방법이다.
두 수 A와 B를 비트 연산하는 경우에는 가장 뒤의 자리부터 하나씩 연산을 수행하면 된다.
(1) 기본 연산
A = 37, B = 83
A = 11011(2), B = 1010011(2)
A & B = 19, A | B = 91, A ^ B = 72
0 0 1 1 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 1 1
& 1 0 1 0 0 1 1 | 1 0 1 0 0 1 1 ^ 1 0 1 0 0 1 1
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 0 1 0 0 0
(2) shift
shift left(<<)와 shift right(>>) 연산이 있다.
A << B (A를 왼쪽으로 B비트만큼 민다)
1 << 0 = 1 (1)
1 << 1 = 2 (10)
1 << 2 = 4 (100)
1 << 3 = 8 (1000)
1 << 4 = 16 (10000)
3 << 3 = 24 (11000)
5 << 10 = 5120 (1010000000000)
A >> B (A를 오른쪽으로 B비트만큼 민다)
1 >> 0 = 1 (1)
1 >> 1 = 0 (0)
10 >> 1 = 5 (101)
10 >> 2 = 2 (10)
10 >> 3 = 1 (1)
30 >> 1 = 15 (1111)
1024 >> 10 = 1 (1)
• A << B 는 A * 2^B와 같다.
• A >> B 는 A / 2^B와 같다. ( (A+B) / 2 는 (A+B) >> 1로 쓸 수 있다)
(3) 정수로 집합 나타내기
정수로 집합을 나타낼 수 있다.
{1, 3, 5, 7, 9} = 2^1 + 2^3 + 2^5 + 2^7 + 2^9 = 570 (1000111010)
{1, 3, 5, 7, 9}에 특정 숫자가 포함되어 있는지 조회하겠다.
• 0이 포함되어 있는지 검사
570 & 2^0 = 570 & (1<<0) = 0 (0이므로 0이 포함되어 있지 않음)
• 1이 포함되어 있는지 검사
570 & 2^1 = 570 & (1<<1) != 0 (0이 아니므로 1이 포함되어 있음)
• 2가 포함되어 있는지 검사
570 & 2^2 = 570 & (1<<2) = 0 (0이므로 2가 포함되어 있지 않음)
• 3이 포함되어 있는지 검사
570 & 2^3 = 570 & (1<<3) != 0 (0이 아니므로 3이 포함되어 있음)
{1, 3, 5, 7, 9}에 특정 숫자를 추가해보겠다.
• 1 추가하기
570 | 2^1 = 570 & (1<<1) = 570 (1이 이미 집합에 있으므로 결과값 변화가 없다)
• 2 추가하기
570 | 2^2 = 570 & (1<<2) = 574 (1000111110)
• 3 추가하기
570 | 2^3 = 570 & (1<<3) = 570 (3이 이미 집합에 있으므로 결과값 변화가 없다)
• 4 추가하기
570 | 2^4 = 570 & (1<<4) = 570 (4가 이미 집합에 있으므로 결과값 변화가 없다)
{1, 3, 5, 7, 9}에 특정 숫자를 제거해보겠다.
• 1 제거하기
570 & ~2^1 = 570 & ~(1<<1) = 568 (1000111000)
• 2 제거하기
570 & ~2^2 = 570 & ~(1<<2) = 570 (2가 이미 집합에 없으므로 결과값 변화가 없다)
• 3 제거하기
570 & ~2^3 = 570 & ~(1<<3) = 562 (1000110010)
• 4 제거하기
570 & ~2^4 = 570 & ~(1<<4) = 562 (1000101010)
{1, 3, 5, 7, 9}에 특정 숫자를 토글해보겠다.(토글 : 0을 1로, 1을 0으로)
• 1 토글하기
570 ^ 2^1 = 570 ^ (1<<1) = 568 (1000111000)
• 2 토글하기
570 ^ 2^2 = 570 ^ (1<<2) = 574 (1000111110)
• 3 토글하기
570 ^ 2^3 = 570 ^ (1<<3) = 562 (1000110010)
• 4 토글하기
570 ^ 2^4 = 570 ^ (1<<4) = 554 (1000101010)
• 정리
현재 집합이 S일 때
i를 검사 : S & (1 << i)
i를 추가 : S | (1 << i)
i를 제거 : S & ~(1 << i)
i를 토글 : S ^ (1 << i)
(4) 연산 우선순위
비트 연산을 사용할 때 연산자 우선순위를 생각해야 한다.
• 1 << N - 1 은
1 << (N - 1) 일까 (1 << N) - 1 일까?
정답은 전자다.
(5) 전체 집합
• 전체 집합 : (1 << N) - 1
N = 5 -> 집합 {1,1,1,1,1}은 31을 의미한다.
이때, (1 << 5) -1 = 31이다.
• 공집합 : 0
