[🗂️기초 자료구조] 1. 비트마스크

비트마스크란?

정수의 이진수 표현을 자료구조로 쓰는 기법입니다. 비트마스크는 엄밀히 말해 자료구조라고 할 수는 없지만 굉장히 유용하게 사용됩니다.

 

비트마스크의 장점

1. 더 빠른 수행시간

비트마스크 연산은 O(1)에 구현되는 것이 많기 때문에 적절히 사용할 경우 다른 자료구조를 사용하는 것보다 훨씬 빨리 동작합니다. 

물론 비트마스크 연산을 사용할 수 있다는 말은 원소의 수가 많지 않다는 뜻이기에 엄청나게 큰 속도 향상을 기대할 수 없지만, 이와 같은 연산을 굉장히 여러 번 수행해야 할 경우에는 작은 최적화도 큰 속도를 가져올 수 있습니다. 

 

2. 더 간결한 코드

다양한 집합 연산들을 반복문 없이 한 줄에 쓸 수 있기 때문에 비트마스크를 적절히 사용하면 굉장히 짧은 코드를 작성할 수 있다.

 

3. 더 작은 메모리 사용량

비트마스크를 이용하는 코드들은 같은 데이터를 더 적은 메모리를 사용해 표현 가능합니다.

더 많은 데이터를 미리 계산해 둘 수 있기 때문에 프로그램도 빨라지고, 캐시 효율도 더 좋습니다.

 

4. 연관 배열을 배열로 대체

불리언 값 배열을 키로 갖는 연관 배열 객체 map<vector<bool>, int>를 사용하고 있다고 치면, 이를 비트마스크를 사용하다면 단순 int[] 배열을 사용해 같은 정보를 나타낼 수 있습니다.

이 기법은 엄청난 시간과 메모리 차이를 가져옵니다.

 

용어 정의 

비트(bit)

이진수의 한 자리, 0 혹은 1의 값을 가질 수 있으며, 컴퓨터가 표현하는 모든 자료의 근간이 됩니다.

 

예) 부호 없는 8비트 정수형 여덟 자리 이진수로 표시할 수 있는 모든 정수를 표현할 수 있습니다.

따라서 부호 없는 8비트 정수형이 가질 수 있는 최소 값은 0, 최대 값은 1111 1111(2) => 255입니다.

 

최상위비트(Most Significant Bit)

부호 없는 N비트 정수형 변수는 N자리의 이진수로 쓸 수 있습니다.

이때 각 비트가 표현하는 값은 2의 0승 ~ 2의 N-1승입니다. 이때 2의 N-1승에 해당하는 비트를 최상위 비트라고 부릅니다.

 

최하위비트(Least Significant Bit)

부호 없는 N비트 정수형 변수는 N자리의 이진수로 쓸 수 있습니다.

이때 각 비트가 표현하는 값은 2의 0승 ~ 2의 N-1승 입니다. 이때 2의 0승에 해당하는 비트를 최하위 비트라고 부릅니다.

 

 

비트 연산자

비트마스크를 사용하기 위해서는 정수 변수를 비트별로 조작할 수 있는 비트 연산자를 사용해야 합니다.

 

AND

AND 연산은 입력받은 두 정수를 한 비트씩 비교하면서, 두 정수에 해당하는 비트가 모두 켜져 있을 때만 결과의 비트를 켭니다.

 

OR

OR 연산은 입력받은 두 정수를 한 비트씩 비교하면서, 두 정수에 해당하는 비트가 하나라도 켜져 있으면 결과의 비트를 켭니다.

 

XOR

XOR 연산은 입력받은 두 정수를 한 비트씩 비교하면서, 두 정수중 하나의 비트만 켜져있을때 결과의 비트를 켭니다.

 

NOT

정수 하나를 입력 받아 켜져있는 비트는 끄고, 꺼져있는 비트는 켭니다.

 

a >> b

정수 a의 비트를 오른쪽으로 b칸씩 밀고 빈 자리는 0으로 채웁니다.

 

a << b

정수 a의 비트를 왼쪽으로 b칸씩 밀고 빈 자리는 0으로 채웁니다.

 

 

유의할 점들

1. 우선순위

C++과 자바에서 &, |, ^ 등의 비트 연산자의 우선순위는 == 혹은 != 등의 비교 연산자보다 우선순위가 낮습니다.

 

int c = (6 & 4 == 4)

 

만일 위 코드를 6 & 4 비트연산 계산 후, 해당 결과 값이 4와 같은 지 확인하는 용도로 짰다면 이는 올바르게 동작하지 않습니다.

비트 연산자가 비교 연산자보다 우선순위가 낮기 때문에 4 == 4가 먼저 계산되고, 결과인 1이 6과 &연산을 하는 식으로 흘러갈 것입니다.

 

올바른 코드

int d = ((6 & 4) == 4)

 

위 코드처럼 비트 연산을 소괄호로 묶어줘야 합니다. 꼭 그게 아니더라도 가독성을 위해서는 소괄호로 묶어주는 것이 좋습니다.

 

 

2. 오버플로우

64비트 정수를 비트마스크로 사용할 때 오버플로우가 발생합니다.

부호 없는 비트마스크 a의 b번 비트가 켜져있는지 확인하기 위한 코드를 다음과 같이 작성했다고 해봅시다.

bool isBitSet(unsigned long long a, int b) {
	return (a & (1 << b)) > 0;
}

 

위 코드는 정상적으로 동작하지 않습니다. 왜일까요 ?

C++에서는 1은 부호 있는 32비트 상수로 취급되기 때문에 b가 32이상이면 1 << b 에서 오버플로우가 발생하기 때문입니다. 

이를 해결하기 위해서는 1뒤에 이 상수가 부호 없는 64비트 정수임을 알려주기 위해 접미사 ull을 붙여 주어야 합니다.

 

3. 부호있는 정수형의 사용

부호 있는 정수형에서 최상위 비트가 켜진 숫자는 음수를 표현합니다.

32비트 정수형에서 하위 20비트만 사용한다든지하는 문제는 별 문제 없지만, 32비트를 전부 사용하고 싶다면 이와 같은 차이는 자잘한 버그를 불러올 수 있습니다.

 

따라서 변수의 모든 비트를 다 쓰고 싶다면 부호 없는 정수형을 쓰는 것이 좋습니다.

 

4. N비트 정수에서 N비트 이상 시프트

얼핏 생각해보면 결과가 0이 되어야 할 것 같지만, C++언어 명세에는 이 결과가 정의되어 있지 않으므로 이런 코드는 환경에 따라 다른 결과를 낼 수 있습니다.

 

비트마스크를 이용한 집합의 구현

비트마스크의 가장 중요한 사용 사례는 집합을 구현하는 것입니다.

N비트 정수 변수는 0 ~ N-1까지의 정수 원소를 가질 수 있는 집합이 됩니다. 이때 원소 i가 집합에 속해있는지 여부는 2의 i승을 나타내는 비트가 켜져있는지 여부로 나타냅니다. 

 

예) 1, 4, 5, 6, 7, 9를 표현하는 정수는 754입니다.

10 1111 0010(2) = 754