비트로 연산하는 방법!
많은 사람들이 비트로 연산하는 것에 대한 두려움과 거부감을 가지고 있는 것 같습니다.
하지만, 비트연산이란 알고보면 별 것 없습니다!
우선, 비트연산을 하기 위해서 알아야할 5가지의 연산 방법을 알아봅시다.
1. & : 비트 AND 연산. 비트마다 AND 연산을 해서 두 비트가 모두 1일 경우에 1 그 외에는 0이 됩니다.
ex) 0b 1111 & 0b 0011 = 0b 0011
2. | : 비트 OR 연산. 비트마다 OR 연산을 해서 두 비트중 하나라도 1일 경우에 1 그 외에는 0이 됩니다.
ex) 0b 1100 | 0b 1010 = 0b 1110
3. ~ : 모든 비트를 1이면 0으로 0이면 1로 반전합니다.
ex ) ~0b 1100 = 0b 0011
4. >> : 1 비트 오른쪽으로 이동합니다.
ex) 0b 110 >> 1 = 0b 011
5. << : 1 비트 왼쪽으로 이동합니다.
ex) 0b 110 << 1 = 0b 1100
참고로 -는 2의 보수를 만드는 연산입니다. 이는, 모든 비트를 반전한 후에 1을 더한 값과 같습니다!
예를 들면, 0001 1010의 값을 가지는 a가 있다고 하면, -a는 1110 0101 + 1 = 1110 0110 이 되는 것입니다!
자 이제 비트 연산에 대해 간단하게 알아 봤으니 과연 어디에 이용하는지 알아볼까요!?
비트 연산은 마치 배열과 같습니다.
int 의 경우에는 32비트의 수로 이루어져있죠.
즉, 32개의 비트에 1과 0으로 정보를 채우는 것입니다. 32개의 bool 배열과 같다는 소리죠!
long long의 경우에는 64비트를 사용하니 64개의 bool 배열과 같다고 생각하시면 됩니다.
그리고 하나의 비트에 1과 0 두개의 수 밖에 채워넣을 수 밖에 없기 때문에, 비트연산을 사용할 때에는 어떤 한 상태가 1과 0 두 가지로만 나타낼 수 있을때 사용 가능합니다!
대표적인것이 조합이죠. 어떤 인덱스를 선택 한다 // 선택 안한다 두가지의 경우만 따집니다.
현재 상태를 체크한 하나의 수 int visit이 있다고 합시다.
이제, 7번 인덱스가 이미 사용되었는지 알고싶습니다!
그렇다면 어떻게 해야할까요!?
7번 인덱스만 추출해야하기 때문에, 1을 7번 쉬프팅한 수와 visit을 &연산 하면 됩니다!
즉, visit & (1<<7) 이 true면 7번 인덱스가 1인지 0인지 알 수 있는 것 입니다.
그렇다면, 7번 인덱스에 1을 체크하고 싶다면 어떻게 해야할까요?
이번에는 visit의 7번 비트에 무엇이 있던지 상관없이 1로 만들어야 합니다.
즉, | 연산을 사용해서 visit | (1<<7)을 하면 됩니다.
이제, 현재 들어온 bit를 이용해서 어떤 연산을 하고 싶다고 합시다.
예를 들면, bit가 1인 부분들의 인덱스에 있는 값들만 모두 더하고 싶다던지.. 이런 경우가 있을 겁니다.
즉, bit에 있는 모든 값들을 이용하는 것 입니다.
이럴 때는, bit 와 1을 &연산을 해서, 해당 값이 true인지 false인지에 따라서 값을 처리하면 됩니다.
그리고 idx를 하나 늘려주고, bit는 오른쪽으로 쉬프팅을 하면, 다음 인덱스에 대해서 계속 연산을 할 수 있죠.
이런 식이죠!
코드를 통해서 봅시다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | void func(int bit){ for(int i = 0; i < n; i++){ if(bit&1){ //process when idx i == 1 } else{ //process when idx i == 0 } bit >>= 1; } } | cs |
i가 123이라고 해서 직접 123을 2진수로 만드는 분이 없길 바라면서!
이만 팁 마치겠습니다.
'공부 > 알고리즘 깨알팁' 카테고리의 다른 글
| [알고리즘 깨알팁] heapify 시간복잡도 계산 (2) | 2020.10.05 |
|---|---|
| [알고리즘 깨알 팁] 코드와 데이터를 분리하자 (테이블 만들기) (7) | 2019.03.13 |
| [알고리즘 깨알 팁] BFS 짜는 법 (4) | 2019.03.12 |
| [알고리즘 깨알팁] 재귀로 1, 2차원 구간 처리하기 (0) | 2019.03.11 |
