비트마스크

작성일 | In

비트마스트

비트연산

  • 비트연산을 사용해서 부분 집합을 표현할 수 있다.
  • &(and), (or), ~(not), ^(xor)
& : 둘다 1 일 경우 = 1
| : 둘다 0이 아닐 경우 = 1
^ : 다르면 = 1, 같으면 = 0
~ : 1이면 0으로, 0이면 1로 변환
  • 두 수 A와 B를 비트 연산하는 경우에는 가장 뒤의 자리부터 하나씩 연산을 수행하면 된다.
  • not 연산의 경우 자료형에 따라 결과가 달라진다. (앞에 0이 있기 때문에)
  • shift left(«)와 shift right(»)연산이 있다.
A << B = shift left = A*2^B
A >> B = shift right = A/2^B
  • 정수로 집합을 나타낼 수 있다.
현재 집합이 S일때
i를 추가 : S | (1 << i)
i를 검사 : S & (1 << i)
i를 제거 : S & ~(1 << i)
i를 토글 : S ^ (1 << i)
{1,3,4,5,9} = 570 = 2^1 + 2^3 + 2^4 + 2^5 + 2^9
570의 부분집합으로 표시할 수 있다.
0 이 포함되어 있는지 검사 : 570 & 2^0 = 570 & (1<<0) = 0
1을 추가하기 : 570 | 2^1 = 570 | (1<<1) = 570
1을 제거하기 : 570 & ~2^1 = 570 & ~(1<<1) = 568
  • 비트마스크를 사용하는 이유는 집합을 배열의 인덱스로 표현할 수 있기 때문이다.
  • 상태 다이나믹을 할 때 자주 사용하게 된다.
배운점 : 비트마스크에 대한 개념을 처음 보게 되었는데, 여럽다. 꼭 다시 볼 것!