[코테] 비트마스킹 기본

비트연산자

• &: AND 연산
• |: OR 연산
• ^: XOR 연산. 같으면 false, 다르면 true
• ~: 모든 비트 반전. 1의 보수연산자
• <<, >>: 비트 이동

★  ~value = -(value + 1)

 

주요 로직

logic	code	description
idx번째 비트 끄기	target &= ~(1 << idx)	idx번째 비트를 0으로 만들고 AND 연산을 통해 끄기
idx번째 비트 XOR 연산	target ^= (1 << idx)	idx번째 비트와 1을 XOR 연산
켜진 최하위 비트 찾기	idx = (target & -target)	-target은 ~target + 1과 같은 결과이다. 따라서 기존 target을 뒤집고 +1을 하면 언제나 마지막에 켜져있는 비트가 켜지고 AND 연산을 통해 찾을 수 있다.
크기가 n인 집합의 모든 비트 켜기	(1 << n) - 1	시프트 연산을 통해 밀고 -1을 하면 모든 비트가 뒤집혀 켜진다.
idx번째 비트 켜기	target |= (1 << idx)	켜는 동작은 해당 비트에 1을 OR 연산하면 켜진다.
idx번째 비트가 켜져 있는지 확인	target & (1 << idx)	켜져 있는지 확인하기 위해서는 1을 통해 AND 연산

 

비트마스킹은 집합에 관련된 연산 또는 경우의 수를 구하는 등 여러 상황에서 사용해 볼 수 있습니다. 두 가지로 상태가 구분되는 경우에도 활용해 볼 수 있습니다.

 

비트마스킹을 활용하면 코딩테스트 중 속도와 메모리 측면에서 이득을 볼 수 있습니다.

 

주의 사항!!

idx번째를 나타내려고 사용하는 1 << idx는 0부터 시작입니다.

연산자 우선순위가 헷갈리는 경우에는 괄호를 잘 써주어야 합니다.

시프트 연산이 있기 때문에 2^n으로 늘어납니다. 따라서 n이 30 이하인 경우에 사용해야 문제가 해결된다고 볼 수 있습니다.