[Algorithm] Bit 연산

Bit연산을 하는 이유

- 컴퓨터에서는 자료를 표현하기 위해 1bit를 활용하며, 1bit는 0 또는 1로 나타난다.

- 이렇게 작은 bit를 활용하여 보다 효율적인 알고리즘을 구현할 수 있다.

 

1. 자료 저장과 집합 표현 용이

- 예를 들어 1~32번 사람이 존재하고, A는 {1, 3, 5, 10}, B는 {2, 3, 5, 31} 번과 친구 관계를 맺는다고 하자. 이때 

  1. A와 B의 모두와 친구인 사람?

  2. A 또는 B와 친구인 사람?

과 같은 문제를 풀 때, 반복문으로 풀 수 있지만 친구 관계를 0 또는 1로 표현하는 Bit-Masking을 함으로써 쉽게 할 수 있다.

 

2. 데이터 압축 및 값의 효율적인 비교

- 두 문자열A, B를 비교할 때는 문자열의 길이 만큼 시간복잡도가 걸린다.

- 이때, 사용하는 문자의 가짓수가 적다면 필요한 bit만 골라내서 정수형 자료에 압축할 수 있다는 것이 특징이다.

- 예를 들어 문자열은 대문자만 주어지며 다음과 같은 문자열 "GALAXY"가 주어질 때, 알파벳끼리 구분하는데는 1~26사이의 값만 필요하다.(A~Z의 개수는 26개)

- 따라서 다음과 같이 압축할 수 있다.

 

 

 

---

비트 연산자

- 크게 6가지 비트 연산자가 존재한다.

- 비트 연산자의 우선순위는 비교 연산자보다 우선순위가 낮다는 점을 주의해야 한다(==, >, <)

Bit Operator	a = 0b1010, b = 0b0100
& (AND)	a & b = 0b0000
| (OR)	a | b = 0b1100
^ (XOR)	a ^ b = 0b1110
~ (NOT)	~a = 0b0101
<< (left shift)	a << n = a * 2^n
>> (right shift)	a >> n = a * 2 ^(-n)

 

---

Bit 연산의 활용

1. 모든 값이 check되었는지 확인

- 10명의 사람이 모두 밥을 먹었는지 확인하고 싶다.

- 이때, bit각 자릿수를 사람으로 두고 밥을 먹었으면 1, 밥을 먹지 않았으면 0으로 두는 이진수로 표현할 수 있다.(배열에 저장하는 대신)

- 총 3가지 방법으로 가능하다. 

a.  다른 하나는 사람수만큼 1로 채운 이진수와 AND연산을 진행한다.

  - 0b1011000101 | 0b1111111111

- 이때 해당 값이 0b1111111111과 같으면, 모든 사람이 밥을 먹었다는 점이고, 그렇지 않다면 아니다.

 

 

2. 모든 값을 1로 만들고 싶을 때

- 이진수의 모든 값을 1로 채우고 싶을 때도 bit연산을 할 수 있다.

- N자리의 1로 채워진 이진수를 만들 때, (0b1 << N) - 1을 진행하면 된다.

  - ex) N = 4, 0b1 << 4 - 1 = 16 - 1 = 15 = 0b1111

 

3. 특정 자릿수의 값이 1인지

- 예를 들어 10명의 사람들 중 2번째의 사람이 밥을 먹었는지 check할 수 있다.

- 예시 : 0b1001000101

  - 여기서 2번째 사람은 밥을 먹었다고 체크되어 있다(LSB부터)

- 이때 3가지 방법이 가능하다.

 

a. 기존 bit & (1 << N) != 0

0b1001000101 & 0b0000000100 = 0b000000010이 나온다.

만약 이때 값이 0이 나온다면, 일치하지 않는다는 의미가 되고, 0이 아니라면 적어도 1번의 and연산이 성공했기 때문에 n번째 자리에 1이 존재할 수 있다는 점으로 해결할 수 있다.

 

b. (기존 bit >> N) & 1 == 1

반대로 이때는 N번째 자리의 수를 LSB로 옮긴 다음 연산을 진행하는 과정이다

0b1001000101 >> 2 = 0b0010010001이 되고, 이때 1과 AND 연산을 진행하면 LSB를 제외한 값들은 모두 0이 되고, LSB의 값에 따라 1 또는 0이 발견된다.

 

c. (기존 bit | 1 << N) == 기존 bit

- 이는 OR연산을 활용해 처리하는 과정이다.

- 0b1001000101 | 0b0000000100 = 0b1001000101이 나와 존재한다는 것을 알 수 있다.

- 이때 만약 N번째 자리가 원래 0이 된다면, OR연산으로 인해 N번째 bit는 항상 1이 되기 때문에, 불일치하는 것을 파악할 수 있다.

 

 

 

---

출처