다시 처음부터!
최근에 카카오에서는 비트마스크 문제를 좋아한다고 해서, 비트마스킹이 뭐지라는 생각에 해당 분야를 살펴봤다.
오랫만에 논리연산자를 다시 공부하게 되었다.
| 연산자 | 역할 | 표기법 |
|---|---|---|
| AND | 두 bit 모두 1 이면 1, 아니면 0 | & |
| OR | 두 bit 중 하나라도 1이면 1 | | |
| XOR | 두 bit가 서로 다르면 1, 같으면 0 | ^ |
| NOT | bit가 1이면 0, 0이면 1 | ~ |
| Left-shift | bit를 왼쪽으로 n칸만큼 옮기고 n칸은 0으로 채운다. | << |
| Right-shift | bit를 오른쪽으로 n칸만큼 옮기고 n칸은 0으로 채운다. | >> |
사실 학부때는 이걸로 논리회로 그리고 요구하는 트랜지스터를 어떻게 만들지, 그리고 계산기 만드는게 마지막이었고 더 이상 다시 볼 일은 없다고 생각했다.
하지만 비트마스크 문제들을 풀다보니 이를 이용해서 문제를 새롭게 풀 수 있었다.
집합
이 문제를 보면 사실 배열이 바로 떠오를 수 밖에 없다. 하지만 배열말고도 풀 수 있는 방법이 비트마스크 이다.
이 문제의 가정이 1 <= N <= 20 의 수를 가지고 추가/삭제/업데이트.. 등 기본적인 문법을 설명하는데 어떻게 배열을 쓰지 않을 것인가 고민했었고, 사실 접근 방법을 정확히 몰라서 여기저기서 개념강좌를 보았다.
추천 링크
여기서는 원소 추가에 대한 개념만 써보려고 한다. 처음에는 종이에 써서 연습해보는게 이해하기도 쉽고 좋은 것 같다.
변수 S = 0 이 있다고 해보자. 여기에 우리는 숫자 3을 추가하고 싶다. 여기서 배열은 쓰일수 없다.
그러면 어떻게 해야할까?
비트마스크!
일단 2진법과 10진법에 대한 개념을 계속 생각하며 접근해야한다.
숫자 3을 배열의 Index라고 생각하는 것이다.
다시 말해 숫자 3을 추가하고 싶다는 것은 배열의 3번째 Index를 1로 바꾼다는 접근 방식이다.(2진법 계산)
현재 0은 20개의 배열이 모두 0이라고 생각 할 수 있는데 3이 추가되었다는 것은 3번째 Idx가 1이 되길 원한다고 생각하면 된다.
S = 0 일 때
00000 00000 00000 00000
1. 배열 인덱스 시작은 오른쪽부터라고 가정
2.편의상 20개 비트만 씀, Int는 64개의 비트를 가지고 있다.
S에 3을 추가
00000 00000 00000 01000 (3번째 idx가 1이 되었다)
이런 식이면 우리는 3을 추가했다는것을 이해한다.
그렇다면 어떻게 추가해야 다음처럼 이해할 수 있을까?
S = S+3 ?? (X)
이 때 그 전에 공부한 비트 연산자를 이용하는 것이다.
바로 << 와 |를 이용해서 말이다.
먼저 0일때와 S가 3을 추가할때를 비교하면 직관적으로는 1000이 추가 된 것이다. 그래서 우리는 1000을 만들 것이다. 다음과 같이 말이다.
1 << 3위의 식은 결국 1비트를 왼쪽으로 3번 옮겨라라는뜻인데 그러면 1000이 된다.
주의1 : 비트 연산자를 쓸 때에는 컴퓨터가 2진수로 계산한다.
(따라서 2 << 3 을 한다고 2000이 되는 것이 아닌 2의 2진수인 10에서 시작하기에 10000 이 된다.)
돌아와서 만들어진 변수 1000을 어떻게 해야 변수 S에 넣을 것인가?
여기서 또다른 비트연산자 OR를 쓴다.
S가 현재 0이기 때문에 (1<<3)과 | 연산을 하면 해당자리수가 1로 바뀐다.
공식
var S = 0
//S에 숫자 N을 추가하려면
S |= (1<<N) 여기서 궁금해서 Print()를 쓸 수 있는데(내가 그랬다) 그러면 10진수로 계산되어서 S는 8값이 나올 것이다. 하지만 계산은 잘 된 것이다. 2진수에서는 3번째 Idx가 1이기 때문에. 2진법이 궁금하다면 print(String(S, radix: 2) 를 이용하면 된다.
주의!2: + 와 | 는 비슷할 수 있지만 전혀 다르다.
var S1 = 0
var S2 = 0
S1 |= (1<<3)
S2 += (1<<3)
print(S1) //8
print(S2) //8위의 코드를 보면 | 말고 + 를 사용해도 같지 않을까라고 생각하지만 이런 경우가 존재한다.
var S1 = 0
var S2 = 0
S1 |= (1<<3)
S1 |= (1<<3)
S2 += (1<<3)
S2 += (1<<3)
print(S1) //8
print(S2) //16
print(String(S1,radix: 2))// = 00000000 00000000 00000000 00010000
print(String(S2,radix: 2))// = 00000000 00000000 00000000 00100000
//같은 수를 또 추가할 경우 +로 하면 자릿수 자체가 바뀐다.이 정도로 추가하는 것을 마무리 하려고 한다.
사실 이 예시는 직접 노가다로 구현하면 더 이해가 빠르다고 생각한다. 여러가지를 추가해서 예시를 보여주려고 한다.
var S:UInt32 = 0
//print(String(S,radix:2) = 00000000 00000000 00000000 00000000
//print(S) = 0
//add 3
S |= (1<<(3)) //1번
//2번 S |= (1<<(3-1))
//나는 2번 방식을 썼는데 1번방식은 보기 직관적으로 편하나 0번째 비트 하나를 아예 사용안한다. 사실 1비트라서 큰 차이는 없을 수도 있지만 32비트까지 가는 수에서는 1번방식을 쓰려면 64비트를 써야한다.
//print(String(S,radix:2) = 00000000 00000000 00000000 00001000
//print(S) = 8
//add 5
S |= (1<<5)
//print(String(S,radix:2) = 00000000 00000000 00000000 00101000
//print(S) = 8+32 = 40
//add 1
S |= (1<<1)
//S = 00000000 00000000 00000000 00101010
//print(S) = 8+32+2 = 42결론
아직 실버문제만 좀 풀어봐서(골드부터는 바로 골드1,2만 있다. ㅎㄷㄷ) 더 풀어봐야겠지만 비트연산을 이용하는 것은 무궁무진하다. 많이 풀어보기도 해야하고 다양하게 접근해봐야 해서 초반에는 접근방식이 어려울 수 밖에 없다고 생각한다. 하지만 이 방법을 이해하면 후에 써먹을 일이 있지 않을까 싶다.
