컴퓨터는 이진법 관련 연산들을 아주 빨리 할 수 있다. 이와 같은 특성을 이용해 정수의 이진수 표현을 자료 구조로 쓰는 기법을 비트마스크(bitmask)라고 부른다.

장점

1. 더 빠른 수행 시간 : O(1)에 구현되는 것이 많다. 비트마스크를 사용할 수 있다는 말은 원소의 수가 많지 않다는 뜻이기에 엄청나게 큰 속도 향상을 기대할 수는 없지만, 연산을 굉장히 여러 번 수행해야 할 경우에는 작은 최적화도 큰 속도 향상을 가져올 수 있다.
2. 더 간결한 코드 : 다양한 집합 연산들을 반복문 없이 한 줄에 쓸 수 있기 때문에 굉장히 짧은 코드를 작성할 수 있다.
3. 더 작은 메모리 사용량 : 데이터를 적은 메모리를 사용해 표현할 수 있다. 이는 더 많은 데이터를 미리 계산해서 저장해 둘 수 있기에 프로그램도 빨라진다. 또한, 더 적은 메모리를 사용하는 프로그램은 일반적으로 캐시 효율도 더 좋다.
4. 연관 배열을 배열로 대체 : map<vector<bool>, int>를 비트마스크를 써서 같은 정보를 정수 변수로 나타내면 단순한 배열 int[ ]를 사용해 같은 정보를 나타낼 수 있다. 엄청난 시간과 메모리의 차이를 불러온다.

용어

부호 없는 N비트 정수형 변수는 N자리의 이진수로 쓸 수 있다. 이때 각 비트가 표현하는 값은 2^0부터 2^(N-1)까지다. 2^(N-1)에 해당하는 비트를 최상위 비트, 2^0을 나타내는 비트를 최하위 비트라고 부른다. 어떤 비트의 위치가 1이라면 해당 비트가 “켜져 있다”라고 말하고, 0이라면 “꺼져 있다”라고 말한다.

연산자

AND : 둘 다 켜져 있으면 켠다

OR : 둘 중 하나라도 켜져 있으면 켠다

XOR : 둘 중 하나만 켜져 있어야 켠다

NOT : 켜져 있으면 끄고, 꺼져 있으면 켠다.

Shift : 비트들은 왼쪽 또는 오른쪽으로 n만큼 움직인다.

C++