비트 연산

비트 (Bit)

• 컴퓨터에서 자료를 표한하기 위해 비트를 사용한다.
• 1bit = 0 또는 1
• 8bits = 1byte

비트 연산자

비트 연산의 종류

• &: AND
• |: OR
• ^: XOR
• ~: NOT
• <<: LShift
• >>: RShift

비트 연산의 우선순위

• 비트연산은 비교 연산보다 우선순위가 낮음에 유의.
• 예) x & y == 0은 x & (y == 0)과 같다.

비트 연산 응용

AND, OR 응용

• 비트 집합 두 개를 AND하면 교집합을 구할 수 있다.
• 비트 집합 두 개를 OR하면 합집합을 구할 수 있다.

XOR 응용

• 같은 값 끼리 XOR하면 0이 되는 특징이 있다.
• XOR을 이용하여 T/F를 번갈아 바꾸는 스위치를 구현할 수 있다.
• XOR을 이용하여 대소문자를 변환 할 수 있다. (ASCII 코드의 특징을 이용)

  char case_convert(char alphabet) {
    return alphabet ^ 32;
  }
  

• XOR을 이용하여 직사각형의 나머지 한 꼭짓점을 구할 수 있다. ()x3 = x0^x1^x2, y3 = y0^y1^y2)
• 권장되지는 않지만 XOR을 이용하여 SWAP을 구현할 수 있다.¹

비트마스킹

1 << n

• $2^n$의 값을 갖는다.
• 원소가 $n$개일 경우 모든 부분집합의 수를 의미한다.
• Power set (모든 부분 집합)
  • 공집합과 자기 자신을 포함한 모든 부분집합
  • 각 원소가 포함되거나 포함되지 않는 2가지 경우의 수를 계산하면 모든 부분집합의 수가 계산된다.

i & (1 << j)

• i의 j번째 비트가 1인지 아닌지를 의미한다.

Bit를 이용한 부분 집합 생성

• 원소 수에 해당하는 N개의 비트를 이용한다.
• n번째 비트 값이 1이면 n번째 원소가 포함되었음을 의미한다.

데이터 압축

• ASCII 코드에서 알파벳만 사용되고 대소문자의 구분이 없는 경우, 마지막 5bits 만으로 표현이 가능하다.
• long long 자료형을 선언하여 최대 12자 길이의 문자열을 압축할 수 있다.
• 한 변수에 압축된 문자열을 저장할 경우, 빠른 문자열의 비교가 가능하다.