[종만북] 비트마스크 / 자료구조 / Python 파이썬

[종만북] 비트마스크 / 자료구조 / Python 파이썬

[종만북] 비트마스크 / 자료구조 / Python 파이썬

 

비트마스크

• 정수 의 이진수 표현을 자료 구조로 쓰는 기법
• 비트마스크는 엄밀하게 말해 자료 구조라고 할수는 없지만, 종종 굉장히 유용하게 사용됨.

 

비트마스크 장점

1. 더 빠른 수행 시간
   • 비트마스크 연산은 0(1)에 구현되는 것이 많기 때문에, 다른 자료 구조를 사용하는 것보다 훨씬 빨리 동작
   • 연산을 굉장히 여러번 수행 해야 할 경우, 작은 최적화로 큰 속도 향상
2. 더 간절한 코드
   • 다양한 집합 연산들을 반복문 없이 한 줄에 쓸 수 있기 때문에 짧은 코드로 작성
3. 더 작은 메모리 사용량
   • 같은 데이터를 더 적은 메모리를 사용해 표현
   • 많은 데이터를 미리 계산해 두어 있으면 프로그램도 속도 향상
   • 캐시 효율 좋음
4. 연관 배열을 배열로 대체
   • 같은 정보를 객체가 아닌 정수 변수로 표현 가능
   • 불린 값 배열을 키로 갖는 연관 배열 객체 -> 정수 변수

 

비트연산자

• a & b   - 두 정수 a, b를 비트별로 AND 연산
• a | b     - 두 정수 a, b를 비트별로 OR 연산
• a ^ b    - 두 정수 a, b를 비트별로 XOR 연산  
• ~a        - 정수 a의 비트열 NOT 언산 결과
• a << b  - 정수 a를 왼쪽으로  b비트 시프트
• a >> b  - 정수 a를 오른쪽으로  b비트 시프트

 

 

비트연산자 예제

• 공집합 & 꽉 찬 집합의 표현

# 공집합
zero = bin(0)
# '0b0'


# 꽉 찬 집합 ( 20 bit )
full = (1 << 20) - 1
print(bin(full))
# '0b11111111111111111111'
# '0b100000000000000000000'(21bit) 에서 1을 뺀 2진수 20bit 전체가 1인 2진수

 

 

• 원소의 포함여부 확인
  • & 연산 사용

# 원소의 포함 여부 확인
# python 은 2진수가 str 형으로 표현됨

a = 1 << 19
# '0b10000000000000000000'
b = 1 << 5
# '0b100000'

if(a & b):
    print('YES')
else:
    print('No')
# No

 

 

• 원소의 삭제
  • OR 연산 사용

# 원소의 삭제

a = int('0b11111', 2)
b = int('0b00100', 2)

c = a & ~b
print(bin(c))
# '0b11011'
# b 의 원소 삭제

 

 

• 원소의토글
  
  • 해당 비트가 켜져 있 으면 끄고, 꺼져 있으면 켜는 것
  • XOR 연산 사용

# 원소의 토글

a = int('0b11011', 2)
b = int('0b00100', 2)

a ^= b
print(bin(a))
# a = '0b11111'

a ^= b
print(bin(a))
# a = '0b11011'

 

 

• 최소 원소 지우기

# 최소 원소 지우기

a = int('0b100100100', 2)

b = a - 1
print(bin(b))
# a = '0b100100100'
# b = '0b100100011'
# b 는 켜져있는 최 하위 bit 를 끄고 그 밑의 bit 를 전부 켠 것

c = a & b
print(bin(c))
# c = '0b100100000'

 

 

• 모든 부분 집합 순회하기

# 모든 부분집합 순회하기
origin = int('0b1101', 2)
subset = origin

while True:
    subset = (subset - 1) & origin

    if subset == 0:
        break

    print(bin(subset))
    # 0b1100 -> 1100
    # 0b1001 -> 1001
    # 0b1000 -> 1000
    # 0b101  -> 0101
    # 0b100  -> 0100
    # 0b1    -> 0001