비트마스크? 그게 뭔데

저학년 때, xor, or , and 와 같은 이진수를 조작하는 연산을 배운적이 있다.

이를 알고리즘 문제를 푸는데 이용하여 수행시간을 빠르고 코드를 짧게 하여 푸는 문제들이 있다. 

 

 

바로 비트마스킹 문제다!!

언젠가 공부해야지 해야지 했는데 이제야 한다. 

 

 

 

1. AND ; 둘 다 1인 경우만 1이 된다. ("&")

 

 

2. OR ; 둘 중 하나라도 1이면 1이 된다. ("|")

 

 

3. XOR ;  두개가 달라야 (1,0 또는 0,1) 1이 된다. ("^")

 

 

4. NOT ; 0은 1으로, 1은 0이 된다. ("~")

 

 

5. shift ; 비트를 왼쪽 혹은 오른쪽으로 움직여 빈자리는 0으로 채운다.  ("<<", ">>")

 

 

 

 

 

---

 

 

전부 1인 배열 만들기 : ( 1<<  a ) - 1

예시) 

A = (1<<10)-1  ; 10크기의 1로 채워져있는 배열 

 

if __name__=="__main__" :
    a = (1<<10)
    b = (1<<10)-1
    print(a)
    print(b)
    print(bin(a))
    print(bin(b))

위 코드를 실행하면 다음과 같은 결과가 나온다. 

 

(1<<10)을 하면 1뒤에 0이 10개가 붙게된다. (즉, 1 1개와 0이 10개) 2^10 == 1024이다. 

여기서 1을 빼면 맨 앞 1이 사라지고 10개의 1이 된다.  (즉, 1이 10개)  (2^10)-1 == 1023 이다. 

 

 

 

 

 

 

 

 

 

백준 비트마스크 문제 :

종이조각  : https://what-am-i.tistory.com/349?category=966524 

[Python/BOJ] 백준 14391 종이조각 _비트마스킹

외판원 순회 

 

 

 

 

 

 

 

 

 

---

 

 

 

 

참고 블로그 :

https://rebro.kr/63

비트마스크 (BitMask) 알고리즘