[algorithm] 비트 연산

비트(bit)

컴퓨터에서 사용되는 데이터의 최소 단위(0 과 1)

비트마스크

• 정수의 이진수 표현을 자료구조로 쓰는 기법으로 빠른 수행시간, 간결한코드, 적은 메모리 사용의 장점을 가짐
• ture/false 나 on/off로 상태를 나타내는 것이 가능
• 부분집합을 배열이 아닌 정수를 통해 나타낼 수 있음

비트 연산(기호는 C언어 기준)

• and : 대응하는 두 비트가 모두 1일때, 1반환

  1010 & 1111 = 1010

• or : 대응하는 두 비트 중 하나라도 1일때, 1반환

  1010 | 1111 = 1111

• xor : 대응하는 두 비트가 서로 다를 때, 1반환

  1010 ^ 1111 = 0101

• not : 비트 값 반전하여 반환

  ~1010 = 0101

• shift : 변수 << 이동할 비트 수 또는 변수 >> 이동할 비트 수 형식으로 사용, 왼쪽 혹은 오른쪽으로 비트 옮겨 반환(연산자 모양 그대로 <<는 왼쪽, >>는 오른쪽 방향으로 옮겨지는 것을 의미하며 왼쪽 shift는 2의 거듭제곱 곱하기, 오른쪽 shift는 2의 거듭제곱 나누기가 됨)

  00001010 << 2 = 101000
  00001010 >> 2 = 000010
  

ref)
1. https://mygumi.tistory.com/361
2. https://dojang.io/mod/page/view.php?id=174