bitmasking

* intro>

💧 bitmask = '컴퓨터는 내부적으로 모든 자료를 이진수로 표현. 이 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법'

(엄밀하게 자료구조는 아님)

 

💧 2진수 관련 bit 연산을 진행하면 웬만한 모든 연산의 time complexity가 $O(1)$로 표현되므로 매우 매우 유용하고 편리함!

 

💧 2진수와 10진수 간의 변환방법 (python)

① 10진수 → 2진수: bin() 함수 사용 (반환 결과 string)

print(bin(100)) #0b1100100 #type 'str'

 

② 2진수 → 10진수

(1) 2진수가 0과 1로 구성된 숫자라면 앞에 0b를 붙이고 출력

(2) 2진수가 문자열 형태라면 int()에 문자열과 2를 지정해 변환

※ bin의 결과가 문자열로 반환되므로, 0b를 붙인 수는 int형이기에 type이 서로 안맞다. 따라서, bin의 결과를 int함수(두번째 인자에 꼭 2를 넣어줘야 함)를 사용해 type을 반드시 맞춰줘야 함!

print(0b1100100) #100
print(int('1100100',2)) #100

* 비트 마스크

→ 장점

① 더 빠른 수행시간

② 더 간결한 code - 다양한 집합 연산들을 반복문 없이 한 줄에 작성 가능!

③ 더 작은 메모리 사용량 - 많은 데이터를 미리 계산해 두어 프로그램 속도 향상, 캐시 효율 good, 같은 데이터를 더 적은 메모리 사용

* 비트 연산자

• AND 연산(&): 대응하는 두 bit가 모두 1일 때, 1 반환
• OR 연산(|): 대응하는 두 bit가 하나라도 1일 때, 1 반환
• XOR 연산(^): 대응하는 두 bit가 서로 다르면, 1 반환
• NOT 연산(~): bit의 값을 반전하여 반환 (1이면 0, 0이면 1)
• 왼쪽 shift 연산(<<): 왼쪽으로 bit를 옮긴다 (2배 곱해지는 의미) (오른쪽 새로 생기는 공간은 0 나옴)
• 오른쪽 shift 연산(>>): 오른쪽으로 bit를 옮긴다 (1/2곱해지는, 즉 2로 나눠지는 의미 + 1이 사라지는 공간은 0 나옴)

* NOT 연산 제외 모든 bit 연산자 복합 연산자 사용 가능! (&=, |=, ^=, <<=, >>=)

* 비트 연산자 예제

① 공집합 / 꽉 찬 집합 표현

→ 함수 bin() 사용 (bin()안에 2진수로 변환하고 싶은 10진수를 넣으면 된다; 앞에 0b는 2진수임을 뜻함)

 

→ 공집합

zero=bin(0)
print(zero) #0b0

 

→ 꽉 찬 집합

ex) 예를 들어 1로 꽉찬 5bit를 표현하고 싶다면(0b11111), 2진수 연산 상 (0b100000 - 0b1) 연산을 진행하면 된다. 0b100000은 1을 왼쪽으로 계속 shift하는 << 연산자를 사용하면 됨 (1<<5)

full=(1<<5)-1
print(bin(full)) #0b11111

 

② 굳이 2진수 0b로 붙여 표현을 안하더라도 10진수 수끼지 비트 연산자 사용할 수 있다. (결과는 동일)

print(0b11 & 0b10) #2
print(3 & 2) #2

* bitmasking 활용 예제>

※ 비트마스킹은 관련 문제를 많이 풀면서 bit operator에 계속 적응을 하는 게 매우 중요하다 ※

 

💧 집합 연산에서, 1부터 N까지 각각의 수가 있다면 해당 자리수에 1, 없다면 0을 입력해 2진수의 연산자를 사용해 checking, removing, adding 등등 다양한 연산을 할 수 있다. 즉, 집합 여부 포함 여부에 따른 계산, 추가, 삭제 연산을 bimasking으로 연산 가능(백준 11723 참조)

💧 학교 과목별 교시가 주어져 있고, 학생별로 쉬는 시간 교시가 주어져 있을 때, 학생이 해당 과목을 들을 수 있는 지의 여부를 bitmasking &연산자로 연산 가능(백준 14569 참조)

* 백준 문제 모음>

→ 계속 업뎃 예정

 

 

 

 

 

 

---

* 내용1) https://dojang.io/mod/page/view.php?id=2460 

* 내용2) https://leeiopd.tistory.com/entry/%EC%A2%85%EB%A7%8C%EB%B6%81-%EB%B9%84%ED%8A%B8%EB%A7%88%EC%8A%A4%ED%81%AC-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC

* 내용3) https://velog.io/@1998yuki0331/Python-%EB%B9%84%ED%8A%B8-%EB%A7%88%EC%8A%A4%ED%82%B9-%EC%A0%95%EB%A6%AC