정의
비트마스킹이란 컴퓨터의 연산 방식인 이진수의 표현을 자료구조 사용하는 기법이다
- 수행시간이 빠름
- 메모리 사용량이 적음
비트마스킹 연산
| 설명 | 코드 | ||
| 1 |
뜻 | 비트를 왼쪽으로 n만큼 이동(2^n) | (1 << n) |
| 예시 | // (1 << 0) == 1 비트를 4만큼 이동하면 10000 |
||
| 2 |
뜻 | n번째 비트 켜기 | num |= (1 << n) |
| 예시 | 10001의 2번째 비트를 키면 10101 | ||
| 3 |
뜻 | n번째 비트 끄기 | num &= ~(1 << n) |
| 예시 | 10111의 2번째 비트를 끄면 10011 | ||
| 4 | 뜻 | n번째 비트가 켜져있으면 True, 아니면 False | if(num & (1 << n)) |
| 예시 | 10101의 2번째 피트가 켜져 있으므로 True | ||
| 5 |
뜻 | n번째를 비트를 반전 (XOR) | num ^= (1 << n) |
| 예시 | 10101의 2번째를 반전하면 10001 | ||
| 6 | 뜻 | n만큼 왼쪽 시프트 한 결과에 1을 빼면 하위 자리의(1 ~ n-1) 비트가 켜짐 |
num = (1 << n) - 1 |
| 예시 | 100000 - 1 = 011111 |
||
| 7 | 뜻 | 켜져 있는 비트 중에서 마지막 비트 추출 | n & -n |
| 예시 | 1011100의 마지막 비트를 추출하면 100 | ||
| 8 | 뜻 | 아래부터 꺼진 비트 켜기 | n | (n+1) |
| 예시 | 0100 -> 0101 -> 0111 -> 1111 | ||
| 9 |
뜻 | 아래부터 켜진 비트 끄기 | n & (n-1) |
| 예시 | 0111 -> 0110 -> 0100 -> 0000 | ||
| 10 | 뜻 | 가장 가까운 꺼져있는 비트의 순번 | int idx = 0; while((n >> idx) & 1) idx++; |
| 예시 | 100111의 가까운 꺼져있는 비트의 순번은 3 | ||
| 11 | 뜻 | 가장 가까이 켜져있는 비트의 순번 (= 가장 가까이 켜져 있는 비트 전의 0의 개수) |
__builtin_ctz(n) |
| 예시 | 100100의 가까운 켜져있는 비트의 순번 2 | ||
| 12 | 뜻 | 켜져있는 비트수 세기 | __builtin_popcount(n) |
| 예시 | 10111의 켜져 있는 비트 수는 4 | ||