알고리즘 문제 해결 전략2 16장 비트마스크(1)

16.1 도입

현대의 모든 CPU는 이진수를 이용해 모든 자료를 표현함. 내부적으로 이진수를 사용하는 컴퓨터들은 이진법 관련 연산들을 아주 빨리 할 수 있음. 이와 같은 특성을 화용해 정수의 이진수 표현을 자료 구조로 쓰는 기법을 비트마스크라고 부름. 비트마스크의 장점은

- 더 빠른 수행 시간

- 더 간결한 코드

- 더 작은 메모리 사용량

- 연관 배열을 배열로 대체

컴퓨터는 모든 정수형 변수를 이진수로 표현함. 컴퓨터가 표현하는 모든 자료의 근간이 됨. 2^(N-1)에 해당하는 비트를 최상위 비트(most significant bit)라고 부르고, 2^0을 나타내는 비트를 최하위 비트(least significant bit)라고 부름. 

비트별 NOT연산은 정수 하나를 입력받아 켜져 있는 비트는 끄고, 꺼져 있는 비트는 켠 결과를 반환함. 비트마스크를 사용하는 식에는 가능한 한 괄호를 자세하게 추가하는 습관을 들이는 것이 좋음. 

 

C++에서 1은 부호 있는 32비트 상수로 취급되기 때문에, b가 32이상이면 식(1<<b)에서 오버플로가 발생함. 아래와 같이 해결 가능함. static_cast는 컴파일 타임에 형 변환을 해줌.

#include <stdio.h>

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

int main()
{

	unsigned long long a = 38335876876;
	int b = 5;
	int result = isBitSet(a, 34);
	printf("%d\n", result);
	return 0;
}

 

또 하나 종종 문제가 되는 것으로 부호 있는 정수형의 사용이 있음. 예를 들면 음수를 오른쪽으로 시프트할 때 왼쪽 끝 비트들이 0이 아니라 1로 채워진다는 차이점이 있음. 따라서 변수의 모든 비트를 다 쓰고 싶을 때는 부호 없는 정수형을 사용하는 것이 좋음.