Quick Syntax
비트 하나를 상태 하나로 볼 때 사용합니다. int는 32비트, long은 64비트이며, 외부 입력으로 받은 비트 위치는 범위를 먼저 검사해야 합니다.
csharp
int mask = 0;
mask |= 1 << 2; // 2번 비트 켜기
bool has = (mask & (1 << 2)) != 0; // 2번 비트 확인
mask &= ~(1 << 2); // 2번 비트 끄기
mask ^= 1 << 2; // 2번 비트 토글
bool isOdd = (x & 1) == 1;
int doubled = x << 1;
int halved = x >> 1;&는 포함 검사, |는 추가, ^는 토글, & ~는 제거에 씁니다. 부분집합 전체 순회는 상태 수가 2^n으로 늘어나므로 원소 수가 작을 때만 선택합니다.
문법
| 연산자 | 이름 | 의미 |
|---|---|---|
& | AND | 둘 다 1인 비트만 1 |
| | OR | 하나라도 1이면 1 |
^ | XOR | 서로 다르면 1 |
~ | NOT | 비트 반전 |
<< | left shift | 왼쪽으로 밀기, 보통 2배 |
>> | right shift | 부호를 유지하며 오른쪽으로 밀기 |
>>> | unsigned right shift | 왼쪽을 0으로 채우며 오른쪽으로 밀기 |
비트 연산은 정수를 2진수 자리의 집합처럼 다룹니다.
text
5 = 0101
3 = 0011
5 & 3 = 0001 -> 1
5 | 3 = 0111 -> 7
5 ^ 3 = 0110 -> 6비트 위치 만들기
1 << k는 k번 위치만 켜진 값을 만듭니다. 코테에서는 이 값을 마스크로 써서 상태 포함 여부를 빠르게 검사합니다. C#은 int 시프트 횟수의 하위 5비트, long 시프트 횟수의 하위 6비트만 사용하므로 1 << 32가 범위 오류가 아니라 1 << 0처럼 계산됩니다. 0 <= k < 32 또는 0 <= k < 64를 코드 밖 전제로 두지 말고 검사하세요.
csharp
int bit0 = 1 << 0; // 0001
int bit1 = 1 << 1; // 0010
int bit2 = 1 << 2; // 0100비트마스크
비트마스크는 여러 개의 true/false 상태를 정수 하나에 담는 방식입니다. 원소 수가 작고 모든 부분집합을 봐야 할 때 자주 사용합니다.
csharp
int n = 3;
for (int mask = 0; mask < (1 << n); mask++)
{
for (int i = 0; i < n; i++)
{
if ((mask & (1 << i)) != 0)
{
// i번 원소가 부분집합에 포함됨
}
}
}| 작업 | 식 |
|---|---|
| k번 비트 켜기 | mask |= 1 << k |
| k번 비트 끄기 | mask &= ~(1 << k) |
| k번 비트 확인 | (mask & (1 << k)) != 0 |
| k번 비트 토글 | mask ^= 1 << k |
| 전체 부분집합 순회 | 0부터 (1 << n) - 1까지 |
주의할 점
C#에서 1 << k의 1은 int입니다. k가 31 이상이거나 더 큰 마스크가 필요하면 1L << k처럼 long을 사용하되, long도 k < 64를 확인해야 합니다.
또 음수에 대한 >>는 부호 비트를 유지합니다. 코테에서 순수한 비트 패턴을 다룰 때는 >>>와 unsigned 타입을 검토하고, <<가 상위 비트를 버려도 overflow 예외를 내지 않는다는 점을 기억하세요.
참고 링크
2 sources