참고자료

https://gus6615.tistory.com/93#:~:text=비트마스크(Bitmask)란%3F,-비트 마스크%3A 비트&text=보통 상태를 표현하거나,상태를 표현할 수 있다.

https://velog.io/@shinyeji28/알고리즘-이론-비트-연산

https://c4u-rdav.tistory.com/30

비트 마스크(Bitmask)란?

<aside> 💡

요약

  1. 비트 연산자
  2. 사용 방법
    1. ckt = 1 << (n-1 ) # 연산하기 위한 n 번째 위치에 1 을 shift #n번째 위치에 아래 동작 수행
    2. &( 원소 확인 ) / | ( 원소 추가 ) / ~ (원소 삭제 ) / ^ (원소 On/off 전환) </aside>

이진수 각 비트(0,1) 구성된 비트 연산을 사용해서 데이터를 효율적으로 처리하는 기법

부분 집합 문제, 그래프 탐색, 상태 전이 등 다양한 문제 해결하는데 사용됨

코테에선 N이 20보다 작을 때, 조합 문제에서 사용 될 수 있음

비트 연산자

| AND | & | | flag확인 비교하는 비트가 둘 다 참일 때만 만족 | | --- | --- | --- | --- | | OR | | | | 비교하는 비트가 둘 중 하나라도 참이면 만족 | | XOR | ^ | | 비교 비트가 둘 중 하나만 참일때 만족 | | NOT | ~ | | 보수 연산 0→ 1 / 1→ 0 | | Left SHIFT | << | A<<B : A *2^B | 변속의 값을 지정된 값의 비트만큼 왼쪽으로 이동 | | RIGHT SHIFT | >> | A>>B : A 2(-B) | 변수의 값을 지정된 값의 비트만큼 오른족으로 이동

<aside> 🤔

비트 기본 연산

1. AND 연산 (원소 확인)

AND (&) : 둘다 1 일때 1임

  1. 1<< 해당 위치 idx : index 위치 한정 값 확인

    ex) 1 <<(n-1) # 3번 위치

  2. 이진수 본인 & (1<< 해당 위치 idx) # 위치 indx 에 값 존재 여부 확인

    1<< 해당 위치 idx : 위치 idex 에 값이 존재하는지 checking 기준

    image.png

my_num = 0b10110101
n = 3 
chk = # n 위치의 값 확인 flag 
if my_num & chk  : 
	# 있음 
else : 
	# 없음

2. OR 연산 (원소 추가) | 빈 상자에 사과 추가

둘 중에 1개만 1여도 1임

  1. 1 << n : 비어있는 곳(0) 엔 1이 추가 , 1이 채워져 있는 곳은 추가 안됨 ⇒ 원래 값 출력
my_num = 0b10110101
n = 4
chk = 1 << (n - 1)
new_num = my_num | chk
print(new_num) # 189
print(bin(new_num)) # 0b10111101

image.png

3. NOT 연산 (원소 삭제 1→ 0)

  1. 원소 삭제 알고리즘 ( NOT 과 AND 연산 혼합)

    {n번쨰 원소 삭제 masking 만들기}

    1. AND : n번쨰 위치에서 원소 존재 확인
    2. NOT : n 번쨰 위치만 0 , 나머지 1로 만들기 # 전체 숫자 뒤집기 # masking
    3. AND 연산 으로 삭제
my_num = 0b10110101
n = 3
# 1. n번쨰 위치 원소 삭제(0) 할 masking 제작
chk = 1 << (n - 1) 
#2. Not & AND 연산으로
new_num = my_num & ~chk
print(new_num) # 177
print(bin(new_num)) # 0b10110001

image.png

4. XOR 연산( 원소 토클 : on/off 상호전환)

  1. AND , OR 등 기존 연산은 기존에 값이 있으면 추가 불가 /빈 공간이면 삭제 불가
  2. XOR 연산 동작 : 값이 있으면→ 삭제 / 값이 없음 → 값 추가
  3. 동작 과정
    1. 1 << (n-1) # 1 을 shit 연산으로 밀어 좋기
    2. XOR 연산 : 0이랑 만나는 부분 → 원래 값 그대로 출력 / 1과 만나는 부분 → 값 뒤집기
    3. 원래 값에서 반전됨
my_num = 0b10110101
n = 3
chk = 0b11 << (n - 1)
print(bin(chk))
new_num = my_num ^ chk
print(new_num) # 185
print(bin(new_num)) # 0b10111001

image.png

</aside>