주말에 모각코(양궁대회)를 진행하던 도중 문제가 안풀려서 이후 풀다가 공부하게 된 bitmasking..
사실 이전에 공부해보려고 링크를 켜놨다가 아마도(?) 크롬 업데이트를 하거나 url이 너무 복잡해서 창을 정리하던 도중 꺼버리고, 까맣게 잊고있다가 다시 공부하게 되었다.
간단히 개념설명, 연산자와 예시를 들어서 설명을 하려고 한다.
테이터의 최소단위는 bit이다. 그리고 bit는 2진의 정보를 말하며 bitmasking은 2진수 연산을 하는 것을 말한다.
python에서 bitmasking을 하는 기본단위는 다음과 같이 쓸 수 있다.
0b10110 # == 22그리고 이에 대한 해석은
1*(2**4) + 0*2**2 + 1*(2**1) + 0*(2**0) = 22
로 나오게 된다. 간단히 맨 오른쪽에서부터 왼쪽으로 갔을 때 n번째 숫자에 1이 들어가있는 경우 2**(n-1)이 된다고 알아두자.
특정 숫자를 간단하게 쓸 수 있는 방법도 있는데 이는 다음과 같다.
k = 5
(1<<k) # == 0b100000 마지막으로 bit를 그대로 썼을 경우 python에서는 자동으로 숫자로 인시하고 해석하므로 예시를 설명하기 위한 내장함수도 예시로 하나 소개해놓는다.
print(bin(0b10010)) # == 0b10010또한 아래 설명하겠지만 연산자에 두 숫자를 그대로 썼을 때 python에서는 이를 bit로 인식해서 해석한다.
print(bin(18)) # == 0b10010이제 python에서 bitmasking에 대한 연산자를 알아보자.
& (and binary 연산자)
두 숫자를 비교했을 때 둘 다 bit에 있는 것을 뽑아주는 연산자이다.
예를 들어
print(0b10101 & 0b11110) # == 20
print((16+4+1) & (16+8+4+2)) # == 20 (16 + 4)
print(bin(0b10101 & 0b11110)) # == 0b10100처럼 사용 가능하다.
| (or binary 연산자)
두 숫자를 비교했을 때 최소 하나의 bit에 있는 모든 수를 뽑아주는 연산자이다.
print(0b10101 | 0b11110) # == 31
print(21 | 30) #위와 동일.
print(bin(0b10101 | 0b11110)) # == 0b11111
print(0b10100 | 0b1010) # == 30
print(20 | 10) #위와 동일.
print(bin(0b10100 | 0b1010)) # == 0b11110이때 모자란 자릿수에는 0이 들어간 것과 동일하다.
print(0b1010 == 0b01010) # == True^ (xor binary 연산자)
같은 두 숫자를 비교했을 때 같은 자리의 bit가 동일한 수일 경우 0, 아닐 경우 1을 뽑아주는 연산자이다.
print(0b11010 ^ 0b1010) # == 16
print(26 ^ 10) #위와 동일.
print(bin(0b11010 ^ 0b1010)) # == 0b10000~ (not 연산자)
워낙 한 숫자에 연산을 했을 때 bit의 최대를 기준으로 1을 0으로, 0을 1로 바꿔주는 연산이라고 알고 있지만, 실재 사용해보았을 때 결과는 1을 더한 후 -1을 곱해주는 연산자.. 아마 binary operation을 생각하면서 만들었기 때문에 두 번째 예시처럼 연산을 하는 것이라고 추측된다..(왜 이렇게 했는지 이유를 알려주실 분 계실까요?..)
print(bin(~ 0b1000)) # WANTED : 0b111, but output : -0b1001
print(~ 0b1000) # WANTED : 7, but output : -9
print((1<<4) + ~ 0b1000) # == 7<<, >> (shift)
bit를 밀어주는 연산자, 맨 아래 밑으로 밀었을 때는 -로 가지 않고 0으로 치부된다.
print(bin(0b1000 >> 2)) # == 0b10
print(bin(0b10 << 2)) # == 0b1000
print(bin(0b1011 >> 3) # == 0b1추천 문제는
programmers 양궁대회
백준 12813번
백준 17285번
백준 1497번
백준 2098번 + DP
겁나 쉬운 문제를 하나 더 찾아서 올립니다.
백준 15917번
추천 문제에 대한 풀이(programmers 양궁대회, 백준 12813번)
