일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- JPA
- database
- 구현
- bigdata
- Transaction
- 백준
- SQL
- 프로그래머스
- S3
- Spring
- Parquet
- MySQL
- EventScheduler
- BFS
- 우선순위큐
- 시뮬레이션
- wrapper class
- ES6
- datanode
- hdfs
- procedure
- greedy
- ACID
- boto3
- namenode
- priorityqueue
- BIT연산
- spark
- Algorithm
- MVC
- Today
- Total
IT 개발일지
[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이 되기 때문에, 불일치하는 것을 파악할 수 있다.
출처