2-4. 비트마스크

비트마스크

비트마스크를 이용해서 부분집합을 구할 수 있다는 점을 기억하고 가자.

• not 연산의 경우 자료형에 따라 결과가 달라진다. 또한, unsigned, signed에 따라서 보여지는 값이 달라진다. signed의 경우 가장 앞 자리 비트를 이용하여 음수/양수를 구별하기 때문이다.
• 정수의 집합을 나타낼 때 사용할 수 있다. 집합에는 같은수가 없기 때문이다. 570을 이진수로 나타내면 1000111010이 되는데, 이는 2^9+2^5+2^4+2^3+2^1로 나타낼 수 있다. 이를 통해서 주어진 수 570를 집합 {1, 3, 4, 5, 9}로 표현할 수 있다.
• 비트마스크를 사용하게되면 정수를 사용하는 것보다, 공간복잡도가 줄어들게 된다.

비트마스크의 연산

• &를 사용하여 비트가 있는지 알 수 있다.
• |를 사용하여 비트를 추가할 수 있다.
• &~를 사용하여 비트를 뺄 수 있다. (2의 보수를 취해준 후 &연산을 한다.)
• ^를 사용하여 비트를 토글한다. 1을 0으로 만들고, 0을 1로 만든다.

비트마스크와 집합

• 비트마스크로 집합을 만들 때, 전체 집합은 (1<<N)-1(2^N-1)이 된다.
• 비트카스크로 집합을 만들 때, 공집합은 0이 된다.

11729 집합, 백준 온라인 저지

비트마스크를 연습해보는 문제이다.

bitset

C++기준으로 int는 32비트, long long은 64비트이다. 64비트를 넘는 비트는 정수로 사용할 수 없다는 의미가 된다. 이런 경우 C++의 bitset을 이용하면 된다.

javascript로도 어렵지 않게 구현할 수 있다. 필요한 경우 bitToArray.js, zerodice0 github를 참조하도록 하자. 회사에서 비트마스크를 사용할 일이 비교적 많았는데, 후배들 중에 bitmask를 어려워하는 경우도 있었고 javascript의 number는 64bits를 온전히 지원하지 않기도 하기에 만든 녀석이다. 구현할 당시에는 몰랐지만 bitset이랑 비슷한 역할을 해준다.

1182 부분집합의 합, 백준 온라인 저지

• 서로 다른 N개의 정수로 이루어진 집합이 있을 때, 이 집합의 공집합이 아닌 부분집합 중에서 그 집합의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 문제이다. (단, 1<=N<=20)
• 모든 집합의 갯수는 2^N개이다. 주어진 N의 최대값은 20이므로, 비트마스크를 사용해서 모든 집합을 구할 수 있다.