비트마스크
비트마스크는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말한다.
이진수는 0 또는 1을 이용하기 때문에 한 비트가 표현할 수 있는 경우는 0과 1 두가지이다. 보통 1은 True를, 0은 False를 나타낸다.
비트 연산
기본 연산 (NOT, AND, OR, XOR)
- NOT : 정수 하나를 입력 받아서 켜져 있는 비트는 끄고, 켜져 있는 비트는 켠다. 기호는 ~
- AND : A와 B를 비교하여 둘 다 켜져 있는 경우에만 켠다. 기호는 &
- OR : A와 B를 비교하여 둘 중 하나라도 켜져 있는 경우에만 켠다. 기호는 |
- XOR : A와 B를 비교하여 둘 중 하나만 켜져 있는 경우에만 켠다. 기호는 ^
시프트 연산(Left Shift, Right Shift)
- Left Shift : 지정한 수만큼 비트들을 전부 왼쪽으로 이동하고 이동되고 남은 비트는 0으로 채운다. 기호는 <<
- Right Shift : 지정한 수만큼 비트들을 전부 오른쪽으로 이동하고 이동되고 남은 비트는 부호 비트로 채운다. 기호는 >>
비트마스크 장점
- 메모리를 적게 사용할 수 있음
- 프로그램이 더욱 빠르게 동작함
- 소스코드가 직관적으로 변경됨
비트마스크를 이용한 집합의 연산
-
S에 X가 있는지 검사
이 말은 곧 S의 X번째 비트가 1인지 0인지 검사하라는 뜻이므로 X번째 비트만 1로 두고 AND 연산을 수행S & (1 << X)
-
S에 X를 추가
이 말은 S의 X번째 비트를 1로 변경한다는 뜻이므로 X번째 비트만 1로 두고 OR 연산 수행S | (1 << X)
-
S에서 X를 삭제
이 말은 S의 X번째 비트를 0으로 변경한다는 뜻이므로 X번째 비트만 0으로 두고 AND 연산 수행S & ~(1 << X)
-
S에서 X를 토글
이 말은 S의 X번째 비트가 0이면 1로, 1이면 0으로 변경한다는 뜻이므로 X번째 비트만 1로 두고 XOR 연산 수행S ^ (1 << X)
-
S에서 모든 원소 삭제
이 말은 S의 모든 비트를 0으로 변경한다는 뜻이므로 S를 0으로 바꿔줌S = 0
-
S에서 모든 원소 포함
이 말은 S의 모든 비트를 1로 변경한다는 뜻이고, 컴퓨터는 2의 보수 체계를 가지고 있어서 -1을 넣어야 모든 비트가 1이 됨S = -1
-
마지막 원소 구하기
이 말은 마지막으로 비트가 1인 지점을 구하겠다는 뜻이고 컴퓨터는 2의 보수 체계를 사용해 1의 보수에서 1을 더한 값이 -S와 동일한 의미를 가짐. 따라서 S와 -S를 AND 연산하면 가장 작은 비트인 마지막 원소를 구할 수 있음.S & -S
-
마지막 원소 삭제
이 말은 마지막으로 비트가 1인 지점을 0으로 변경한다는 뜻이고 가장 마지막 비트만 0으로 바꾸고 나머지는 그대로 둬야함.S &= (S - 1)
참고
https://github.com/gyoogle/tech-interview-for-developer/blob/master/Algorithm/%EB%B9%84%ED%8A%B8%EB%A7%88%EC%8A%A4%ED%81%AC(BitMask).md
https://rebro.kr/63
https://gyyeom.tistory.com/
https://hstory0208.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B9%84%ED%8A%B8%EB%A7%88%EC%8A%A4%ED%81%ACBitMask%EB%9E%80
https://coding-food-court.tistory.com/193
