: 이진수 표현을 자료 구조로 쓰는 기법

엄밀히 말해서는 자료구조는 아니지만, 빠른 연산을 위해서 유용히 사용된다.

장점

• 빠른 수행시간: 적절히 사용할 경우 다른 자료구조보다 빨리 동작. (O(1))
• 간결한 코드: 반복문을 한줄에 쓸 수 있음.
• 더 작은 메모리 용량: 더 적은 메모리는 더 많은 데이터를 미리 계산할 수 있다는 것. → 프로그램의 성능 증가
• 연관 배열을 배열로 대체: 불린 값 배열을 키로 갖는 map 객체를 단순히 비트마스크를 써서 같은 정보를 정수 변수로 나타내면 단순한 배열 int를 사용해 같은 정보를 나타낼 수 있다. → 이 기법이 엄청난 시간과 메모리 차이를 불러온다.

용어 정의

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

이때 각 비트가 표현하는 값은 $2^0$부터 $2^{n-1}$ 까지이다.

• $2^0$비트: 최하위 비트
• $2^{n-1}$비트: 최상위 비트

어떤 정수를 이진수로 표현했을 때, 어떤 비트의 위치가 1 → 켜져있다, 0 → 꺼져있다 라고 표현한다.

비트 연산자: 비트 마스크를 연산하기 위한 연산자

→ AND(&), OR(|), XOR(^), NOT(~), SHIFT(>>, <<)

주의할 점

• 자바, C++등 에서는 비트 연산자의 우선순위가 ==, ≠ 등의 비교 연산자보다 낮다.

  따라서 비트연산자 사용시 괄호를 잘 써주는게 좋다.

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

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

  다음은 a의 b번 비트가 켜져있는지 확인하기 위한 식이지만, 정상적으로 작동하지 않는다. C++에서는 1은 signed 32비트 상수로 취급되서, b가 32이상이면 1 << b의 식이 overflow가 발생하기 때문이다. 따라서 64비트 정수라는 것을 알려주는 접미사 ull을 붙여주어야 한다.

• 부호있는 정수형 사용시 문제 발생 → 왠만하면 unsigned를 쓰는게 좋다.

  부호있는 정수형의 경우 최상위 비트가 켜진 수는 음수이다. 32비트를 전부 사용할 때 자잘한 버그들을 불러올 수 있다.

  ex) 음수를 오른쪽으로 시프트 할때, 왼쪽 끝 비트들이 0이 아닌 1로 채워질 수 있다.

파이썬에서 비트마스크 쓰기