백준 11723번 집합

< 백준 11723번 집합 - 마포 코딩박 >

사용한 알고리즘: 비트마스킹


 비트마스킹을 이용해 문제에서 요구하는 연산을 하는 문제였습니다.

문제풀이는 다음과 같습니다.
(1) (코드 14~18)
 add : 비트 연산자 | (or) 을 사용해줍니다.

(2) (코드 19~23)
 -1 = 111...11 로 저장됩니다. -1 + 1 = 1000....00 = 0 으로 계산되죠! 이를 이용하면 -1-(1<<x) = 111...11 - (1<<x) = 111....101111 로 x번째가 0 이 됩니다.
 따라서 remove : val&(-1-(1<<x)) 를 하게되면 x번째가 0 이 됩니다.

(3) (코드 24~42)
 check 연산은 & (and) 연산자로, toggle 연산은 ^ (xor) 연산자로 해주면 됩니다.
 all 연산은 위에 말한대로 -1 = 111...11 이므로 이를 활용해줍니다.