[알고리즘] 비트마스크???!!!

비트마스크(bit mask)

비크마스크란 무엇인가?

• 정수를 이진수로 표현, 비트 연산을 통해 문제를 해결해 나가는 기술.
• 집합에서 하나의 원소는 하나의 bit로 표현(꺼져있다, 켜져있다.)

ex

switch_states = [True, False, False, True, True, False, False, False, True, True]


switch_states = 0b1001100011  # 611, python에서는 앞에 '0b'를 붙여 이진수 표현 가능

정수형으로 표현하면

• 비트연산을 통한 삽입, 삭제, 조회 등이 간단해짐
• 더 간결한 코드 작성이 가능
• 더 빠른 연산이 가능
• 더 작은 메모리의 사용.
• 비트마스크를 이용한 정수 표현으로 다이나믹 프로그래밍이 가능함. (중요)

위와같은 장점이 있습니다.

---

비트 연산.

AND(&)

bin(0b1010011010 & 0b1101101100)  # 0b1000001000

둘다 1이면 1반환.

OR(|)

bin(0b1010011010 | 0b1101101100)  # 0b1111111110

하나라도 1이면 1반환.

XOR(^)

bin(0b1010011010 ^ 0b1101101100)  # 0b111110110

서로 다른 숫자면 1반환.

SHIFT(>>, <<)

bin(0b0010 << 2)  # 0b1000
bin(0b1100 >> 2)  # 0b11

<<는 왼쪽 2진수를 n칸만큼 밀어내는것이고(2^n만큼 곱한다)

/>>는 오른쪽으로 n칸만큼 당긴다. (2^n으로 나눈다)

NOT(~)

bin(~0b0010)  # 0b1101

비트값을 반전시킵니다.

---

비트연산 응용

원소 추가(비트 켜기)

n = 3
print(bin(0b0010 | (1 << n)))  #  0b1010

n번째 수를 추가 하고자 할 때

(1<<n)은 2^n을 의미한다.

(원소가 n개인 모든 부분집합의 수. = 각원소가 포함되거나 안되는 부분집합의 수)

원소 제거

n = 3
print(bin(0b1010 & ~(1 << n)))  #  0b10

n번째 수를 제거 하고자 할 때

원소 조회

n = 3
print(bin(0b1010 & (1 << n)))  #  0b1000

n번째 수가 있나 없나 확인 할 때 (0이면 없고, 1 이상이면 있는 것)

i & ( 1 << j ) i의 j번째 비트가 1인가?

원소 토글

n = 3
print(bin(0b1010 ^ (1 << n)))  #  0b10

n번째 수를 켜져 있으면 끄고, 꺼져 있으면 켬

뺄셈.

-3 = (~3+1)

-3은 (3의 보수+1)

두 집합에 대해 연산

A | B       → A와 B의 합집합
A & B     → A와 B의 교집합
A & (~B) → A에서 B를 뺀 차집합
A ^ B     → A와 B중 하나에만 포함된 원소들의 집합 

모든 부분 집합 순회하기

for (int subset = A ; subset ; subset = ((subset - 1) & A)){ }

최소원소 찾기, 지우기

first = A & (-A);
A &= (A - 1);

공집합과 꽉찬집합 구하기.

    A = 0;
    A = (1 << n) - 1;//n개의 비트 모두 켜는 방법.

정수의 2의 지수승 여부 확인하기(2^k꼴인지.)

def is_exp_binary(n):
    return n & (n - 1) == 0

ex.) 예제 테트리스 벽돌 출력하기

# 테트리스 벽돌을 출력해보자
brick = (0x0660, 0x0F00, 0x2222, 0x6220, 0x4460, 0x4640, 0x7200, 0x6300,0x4620)
for i in brick:
    mask = 0b1000000000000000
    for j in range(0,16):
        print('■' if (mask & i) == mask else '□', end='')
        if (j+1)%4==0:
            print()
        mask >>= 1
    print()

---

비트마스크 에라토스테네스 체

기존의 방식

SIZE = 2 ** 16
SIZE_SQRT = int(SIZE  ** (1/2))
sieve = [1 for _ in range(SIZE+1)]
sieve[0] = sieve[1] = 0
TEST = 20


for i in range(2, SIZE_SQRT+1):
    if sieve[i] == 1:
        for j in range(i*i, SIZE+1, i):
            sieve[j] = 0

for i in range(2, TEST+1):
    print(f"{i:>3} : {'prime' if sieve[i] else 'composite'}")

-> 비트마스크로 배열 하나에 여러 숫자의 소수여부를 담으면 배열의 크기를 줄일 수 있다.

# 1.
SIZE = 2 ** 16 + 1 # Size is too big... Isn't it?

# 2.
sieve = [255 for _ in range(SIZE // 8 + 1)]

# 3.
def set_composite(n):
    sieve[n >> 3] &= ~(1 << (n & 7))

# 4.
set_composite(0)
set_composite(1)

# 5.
def is_prime(n):
    return True if sieve[n >> 3] & (1 << (n & 7)) else False

# 6.
for i in range(2, int(SIZE ** (1/2))+1):
    if is_prime(i):
        for j in range(i*i, SIZE+1, i):
            set_composite(j)

이 알고리즘의 핵심 아이디어는 기본적인 구현이 체의 한 원소에 0과 1, 즉 1비트만 담음으로써 단 한 개의 자연수의 소수 여부만 담을 수 있던 것과 달리 비트마스크 구현은 한 원소에 8비트씩을 담음으로써 8개의 자연수의 소수 여부를 파악할 수 있고 따라서 필요한 배열(체)의 크기를 8분의 1로 줄일 수 있다는 것이다.

그건 그렇다치고, 이제 이것을 어떻게 실현하는가가 문제이다. 해결해야 하는 주된 문제는 이것이다.

체가 판별하려는 최대 숫자가 SIZE 이고 내가 현재 판별하고자 하는 숫자가 n일 때

1. 현재 체의 크기는 *SIZE / 8* 일텐데, 내가 원하는 *n* 은 체의 몇 번째 원소에 들어 있는가?
2. 해당하는 원소를 찾았을 때 원소 안의 8비트 수의 어느 비트가 내가 원하는 *n* 의 소수 여부를 담고 있는가?

이 두 문제를 해결하면 동시에 해결하면(AND) 우리가 원하는 수의 소수 여부를 찾을 수 있다.

먼저 1번. 원하는 수는 체의 어느 원소에 들어있을지. 일반적인 구현에서는 단순히 sieve[n] 을 통해 그 여부를 알 수 있었는데 지금은 단순히 n 을 넣어서는 안 된다. 여기서는 *sieve[n >> 3]* 를 통해 원소 위치를 찾을 수 있다. 사실 ‘n >> 3’은 기능상 ‘n // 8’과 일치한다.

2번. 체의 원소를 찾았을 때 8비트에서 내가 원하는 원소는 어느 비트에 위치할지. 이는 ‘1 << (7 & n)’으로 찾을 수 있다. ‘7 & n’을 통해 n 의 7과의 접점을 찾는다. 그러니까 둘의 ‘&’ 연산은 0부터 7까지의 값을 내놓을 것이고, 이는 사실상 ‘n % 8’과 같다. 그 나머지를 ‘(1 << ‘ 연산으로 원소의 8비트 이진수에서 원하는 비트에 접근할 수 있다.

이 1번과 2번의 교집합을 찾으면 수많은 수에서 우리가 원하는 바로 그 수의 소수 여부를 판단할 수 있다. 코드를 살펴보자.

각 부분을 살펴보자.

1. 먼저 체의 크기 SIZE 는 2의 16승이다. 대단한 의미는 없다.
2. 체의 크기를 ‘SIZE // 8’ 로 잡는다. 그리고 각 원소를 255로 초기화한다. 255는 8개의 비트를 모두 1로 켠 수이며 기본적인 구현에서 각 원소를 1로 초기화한 것과 일맥상통하다.
3. 원하는 수 n 합성수로 설정하는 set_composite 함수를 만들었다. 이 함수는 먼저 n 이 속한 체의 원소를 찾고(‘sieve[n >> 3]’), 그 수에서 n 이 속한 비트를 0으로 설정한다.(‘&= ~(1 << (n & 7)’). 이 코드는 몇 가지 예를 만들어 실험해보라.
4. 그리고 0과 1은 소수가 아니기 때문에 합성수로 설정한다. 엄밀히 말해 0, 1 모두 합성수는 아니지만 이 예제에서는 소수가 아닌 것만 확인하면 된다.
5. n 이 소수인지 판단하는 is_prime 함수를 만든다. 이는 앞서 살펴 본 1번과 2번의 교집합(‘&’)을 살핀다. 교집합 비트가 0이면 소수가 아니고, 0이 아니면 소수다.
6. 2부터 각 수에 대해 체 작업을 한다. 이는 기본적인 구현의 알고리즘과 본질적으로 같다.

한 번 테스트해보라.