개발/알고리즘
비트마스크 알고리즘
차가운콩
2025. 5. 11. 23:42
오늘은 비트마스크에 대해서 공부하며 기록을 할 것입니다.
비트마스크란 무엇일까요
비트마스크
비트마스크(Bitmask)는 컴퓨터 알고리즘에서 매우 효율적인 방법입니다
2진순의 비트를 이용하여 상태를 표현하고 조작하는 기법입니다.
비트마스크의 장점
- 메모리 효율성: 작은 집합을 표현할 때 매우 효율적인 메모리를 사용할 수 있습니다.
- 연산 속도: 비트 연산은 CPU에서 매우 빠르게 처리할 수 있습니다.
- 간결한 코드: 복잡한 집합 연산을 간결하게 표현할 수 있습니다.
주요 비트 연산자
- AND ( & ): 두 비트가 모두 1인 경우에만 1을 반환 합니다.
- OR ( | ): 두 비트 중 하나라도 1인 경우에 1을 반환 합니다.
- XOR ( ^ ): 두 비트가 서로 다른 경우 1을 반환 합니다.
- NOT( ~ ): 비트를 반전 시킵니다. (0 -> 1, 1 -> 0)
- 왼쪽 시프트 ( << ): 비트를 왼쪽으로 이동
- 오른쪽 시프트 ( >> ) 비트를 오른쪽 이동
최상위 비트(Most Significant Bit, MSB)
최상위 비트는 이진수에서 가장 왼쪽에 위치한 비트를 말한다.
- 부호 있는 수 표현에서는 부호를 표현한다.
- 2의 보수법에서는 MSB가 0이면 양수, 1이면 음수
- 부호 절대값에ㅐ서도 MSB가 0이면 양수, 1이면 음수
부호 절대값
- 부호절대값은 이진수에서 음수를 표현하는 한 방법이다.
- 가장 왼쪽 비트(최상위 비트)가 부호 비트로 사용된다.
- 0은 양수를, 1은 음수를 나타낸다.
- 나머지 비트들은 절대값(크기)을 표현한다.
예를 들어, 8비트 부호 절대값 표현에서:
- +42는 00101010로 표현됩니다 (맨 앞의 0은 양수를 의미)
- -42는 10101010로 표현됩니다 (맨 앞의 1은 음수를 의미)
부호 절대값 방식은 단점은 0을 표현하는 방법이 두가지이고, 덧셈과 뺼셈같은 산술 연산이
복잡해진다.
보수 (Compledent)
- 어떤한 기준값에서 해당 수를 뺀 값
- 어떤 수를 맞추기 위해 보충되는 수
2진법에서 010101 이라고 한다면 1의 보수는 그 비트를 반대로 1을 0으로 0을 1로 하는 것이다
010101은 21의 값이고 그 반대의 값은 101010 일 것이다.
101010 = -32(최상위 비트) + 8 + 2 = -22라는 결과가 나온다
그래서 ~N은 -N -1과 같다.
최상위 비트를 포함하여 비트의 값을 덧셈한다.
21을 9의 보수라고 생각해보자
그럼 99 - 21를 한다면 78이라는 값이 나올 것이다.
21의 10의 보수는 ?
100 - 21을 한다면 79라는 값이 나온다
즉 N의 보수 + 1 = N+1 보수와 같다
이 말은 21을 010101을 1의 보수로 한다면
1의 보수 + 1 = 2의 보수
101011은 2의 보수이다.
N진법에서는 N-1의 보수와 N의 보수만을 정의합니다.
- 2진법은 1의 보수와 2의 보수
- 10진법은 9의 보수와 10의 보수
비트마스크의 집합 기본 연산
- 원소 추가: S |= (1 << i ) - i번째 원소를 집합 S에 추가합니다.
- 원소 제거: S &= ~(1 << i ) - i번째 원소를 집합 S에서 제거합니다.
- 원소 토글: S ^= (1 << i ) - i번째 원소가 있으면 제거, 없으면 추가가 됩니다.
- 원소 포함 여부 확인: if (S & (1 << i )) - i번째 원소가 S에 포함되어 있는지 확인합니다.
- 전체 집합 생성: S = (1 << n ) - 1 (0 ~ N -1까지의 원소를 포함합니다.
비트 연산자의 시프트 연산
- LEFT SHIFT 10(00001010) << 1은 20(00010100)이라는 값, 즉 2로 곱함
- RIGHT SHIFT 20(00010100) >> 1은 10(00001010) 이라는 값, 즉 2로 나눔
연산자의 우선 순위
