April 27, 2021 ( last updated : April 27, 2021 )
비트마스크
bitmask
https://github.com/sneakstarberry/
[알고리즘] 비트마스크 기법
이진수 표현을 다양하게 쓰는 기법을 비트마스크(bitmask)라고 부릅니다. 비트마스크는 약간의 메모리와 수행시간의 차이를 불러올 수 있습니다. 그리고 무엇보다도 코딩 테스트에 종종 나옵니다.
비트 마스크릴 사용하기 위해서는 정수의 변수를 비트 별로 조작할 수 있는 비트 연산자를 사용해야합니다.
비트 연산으로는 AND, OR, XOR, NOT, SHIFT 있습니다.
AND 연산자는 두 정수를 한 비트씩 비교, 두 정수의 비트가 모두 켜져 있을 때만 결과의 비트를 킵니다.OR 연산자는 두 정수를 한 비트씩 비교, 두 정수의 비트 중 하나라도 켜져 있을 때 결과의 비트를 킵니다.XOR 연산자는 두 정수를 한 비트씩 비교, 하나는 켜져 있고 하나는 꺼져 있을 경우 결과 비트를 킵니다. 둘 모두 켜져 있을 때 결과 비트를 끕니다.NOT 연산자는 단항 연산자로 비트가 켜져 있을 경우 끄고 꺼져 있을 경우 킵니다.SHIFT 연산자는 정수의 비트 들을 왼쪽 또는 오른쪽으로 원하는 만큼 움직입니다.| 연산 | 코드 |
|---|---|
| a,b를 AND 연산 | a&b |
| a,b를 OR 연산 | a | b |
| a,b를 XOR 연산 | a^b |
| a의 NOT 연산 | ~a |
| a를 왼쪽으로 b비트 만큼 시프트 | a«b |
| a를 오른쪽으로 b비트 만큼 시프트 | a»b |
상수 0을 통해서 공집합을 나타낼 수 있습니다.
0
20개의 비트가 모두 켜진 정수를 만들겠습니다. (1 «20) - 1
원소를 추가 한다는 것은 비트를 킨다는 것입니다. 따라서
OR연산을 통해서 꺼져있는 비트를 킬 수 있습니다.
집합 |= 1 « p;
원소를 삭제 한다는 것은 비트를 끄는 것입니다. 비트를 키는 것보다는 복잡하게 끌 수 있습니다. 먼저 끄고자 하는 비트를 나타냅니다.
1 « p
이제 NOT연산을 통해서 p번째 비트 이외에는 모두 비트를 켜주고 p번째 비트는 꺼줍니다.
~(1 « p)
이후
AND연산자를 통해서 집합으로 부터 특정 비트만 빼줄 수 있습니다.집합 & ~(1 « p);
원소의 포함여부는 확인하고자 하는 원소를 표현하고
1 « p
집합과
AND연산자를 통하여서 해당 원소가 없다면 0이 나오고 원소가 있다면1 << p에 해당하는 값이 나오게 된다.집합 & (1 « p)
해당 비트가 켜져 있으면 끄고 꺼져 있으면 켜는 방법입니다.
XOR연산을 통해서 해당 방법을 구현할 수 있습니다.집합 ^= (1 « p);
int bitCount(int x) {
if(x == 0) return 0;
return x % 2 + bitCount(x / 2);
}
int 최소원소 = (집합 & -집합);
집합 &= 집합 - 1
for(int 부분집합 = 집합; 부분집합; 부분집합 = ((부분집합-1) & 집합)){}
Originally published April 27, 2021
Latest update April 27, 2021
Related posts :