비트 연산

황상진·2022년 7월 22일
0

Algorithm

목록 보기
8/8
post-thumbnail

비트 연산

비트(bit)

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

비트 연산자

  • 비트 연산의 우선순위에 주의가 필요합니다. 일반적으로 사용하는 사칙연산 +, -, *, /은 비교, 논리 연산자(==, >, && 등)보다 우선순위가 높습니다. 하지만 비트 연산은 논리 연산보다 우선순위가 높으나 비교 연산보단 낮습니다.

비트 연산 응용

& AND, | OR

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

^ XOR

  • true/false를 번갈아 바꾸는 스위치를 구현할 수 있습니다.
  • XOR 연산을 이용해서 대소문자 변경을 해줄 수 있다.
  • 대문자의 아스키 코드는 모두 여섯번째 비트가 0이고 소문자의 경우에는 여섯 번째 비트가 모두 1이다. 따라서 XOR 연산을 이용하여 문자의 여섯 번째 비트를 바꿔주면 대소문자가 바뀌게 된다.
//대소문자 변경해주는 함수
void converAlpha(char c){
	return c^(1<<5);
}
  • 3점의 x,y좌표가 주어진 직사각형의 나머지 한 번의 좌표를 구하는 것도 XOR 연산으로 가능합니다.
  • XOR 연산은 교환 법칙이 가능하고, a^a = 0, a^0 = a 입니다.
struct point{
	int x;
    int y;
};

void findRestPoint(point a,point b, point c){
	int tx,ty;
    tx = a.x ^ b.x^ c.x;
    ty = a.y^ b.y^ c.y;
    return point temp{tx, ty};
}

~ Not

  • 비트 집합에 사용하면 가지고 있지 않은 원소들을 구할 수 있습니다.

<<, >> Shift

  • 2의 거듭제곱 곱셈/나눗셈
  • 정수 자료형을 왼쪽으로 i칸 밀거나 오른쪽으로 i칸 미는 연산은 각각 2^i를 곱하거나 2^i로 나누는 연산과 같습니다. 특히 / 연산은 느리므로 나누는 수가 2의 거듭제곱일 경우 >>로 바꾸면 성능 향상을 얻을 수 있습니다.
    마찬가지로 %(나머지) 연산도 나누는 수가 2의 제곱수일 경우 &로 바꿀 수 있습니다.

비트 마스킹

  • 각 Bit를 하나의 Flag로 활용한다면 자료 저장과 집합 표현을 쉽게 할 수 있습니다.

데이터 압축

  • 문자열 두 개를 비교하는 데에는 O(문자열의 길이)의 시간이 듭니다. 만약 사용하는 문자의 가짓수가 적다면 필요한 bit만 골라내서 정수형 자료형에 압축할 수 있습니다.

  • 예를 들어 문자열이 알파벳 대문자로만 이루어졌다면 알파벳끼리를 구분하는 데에 1이상 26이하의 값만 필요합니다. 이는 5bits 만으로도 표현할 수 있죠.

profile
Web FrontEnd Developer

0개의 댓글