비트연산 / 비트마스킹

1. 비트연산

 1.1 비트 ( bit ) 

   비트란 컴퓨터에서 자료를 표현하기 위해서 비트를 사용합니다.

   1 bit = 0 또는 1

   8 bit = 1byte

 

 1.2 비트 연산자

   & , | , ^ , ~ , >> , << 이 있다. 

  >> 는 2의  n 승을 곱하고 나눈것과 같다

 1.3 연산자의 우선순위

  사칙연산 >  비교연산자 =  논리연산자.

  비교연산자 > "비트연산자"  > 논리연산자

 

 1.3 비트연산 응용

   ex ) 대문자의 아스키 코드는 모두 여섯번째 비트가 0이고 소문자의 경우에는 여섯 번째 비트가 모두 1이다.

          따라서 XOR 연산을 이용하여 문자의 여섯 번째 비트를 바꿔주면 대소문자가 바뀌게 된다.

char case_convert(char alphabet) {
	return alphabet ^ 32;  // 32 는 이진수로 100000
}

    NOT ) 음의 인덱스로 사용할 수 있다.

std::vector<int> vec {0,1,2,3,4};
for ( size_t i = 0 ; i < vec.size(); i++){
  printf("%d %d\n" , vec.begin()[i] , vec.end()[~i]);
}

   SHIFT ) 나누거나 곱하는 수가 2의 n승일 경우 쉬프트 연산으로 성능 향상을 얻을 수 있다.

// WARNING 음수일 때 제대로 동작하지 않음
void div(int num, int x) {
	printf("%d / 2^%d = %d ... %d\n", num, x, num >> x, num & ((1 << x) - 1));
}

 

2. 비트마스킹

각 Bit를 하나의 Flag 로 활용한다고 생각해보자. 자료 저장과 집합 표현을 쉽게 할 수 있다.

각각 친한 친구들의 번호가 주어진다고 하자.  ( 사람은 0~31까지) 

 1. A와 B가 모두 아는 친구는? 

 2. A또는 B가 아는 친구는 ? 

비트연산을 사용하면 이런 집합 연산이 간단해짐. 

우리는 반복문 없이도 문제 풀이가 가능해진다.

 

3. 데이터 압축

문자열 두개를 비교하는데 문자열 길이만큼의 시간이 든다. 사용하는 문자의 가짓수가 적다면, 필요한 bit들만 골라내서 정수형 자료형에 압축할 수 있다.

예를 들면 문자열이 알파벳 대문자로만 이루어 졌다면, 알파벳끼리 구분하는데 1이상 26이하의 값만 필요하다.

이는 5bit 만으로도 알파벳끼리 구분이 가능하다는 것이다.

long long compress(char str[13]){
  long long res = 0; 64 )
  // size_t 는 메모리나 문자열 등의 길이를 구할 때에는 "unsigned int" 대신 size_t 라는 형으로 길이가 반환 운영체제의 bit에 따라 크기가 결정됨
  for ( size_t i =0 ; i < 12 ; i ++){    
    res = (res << 5 ) | (str[i] ^ 64);
  }
}