비트 마스킹(Bit Masking)

 

비트 마스킹 (Bit Masking)

0b10  # 2
0b11  # 3
0b110 # 4

정수의 이진수 표현을 자료구조로 사용하는 방법

컴퓨터는 모든 데이터를 0과 1로 가지고 있기 때문에 정수 역시 0과 1로 표현됩니다.

이러한 비트를 이용해 자료구조로 활용하는 방법을 비트 마스킹이라고 합니다.

 

파이썬에서 2진수는 앞에 '0b'를 붙여 나타낼 수 있습니다.

 

비트 연산자

비트 연산은 AND, OR, XOR, NOT, LEFT SHIFT, RIGHT SHIFT 연산이 있습니다.

 

AND &

 

0b110 & 0b010 # 0b010

    0b110
& ) 0b010
    -----
    0b010

 

AND 연산자 &는 두 이진수에서 동일한 위치에 1을 가진 것만 1로 만듭니다.

 

OR |

 

0b001 | 0b010 # 0b011

    0b001
| ) 0b010
    -----
    0b011

 

OR 연산자 |는 두 이진수가 가진 모든 1을 반영합니다.

 

XOR ^

 

0b101 ^ 0b110 # 0b011

    0b101
^ ) 0b110
    -----
    0b011

 

XOR 연산자 ^는 두 이진수에 대해 같은 위치에서 값이 다를 때 1을 표시합니다.

 

NOT ~

 

~0b101 # 0b010

 

NOT 연산자 ~는 1을 0으로 0을 1로 바꿉니다.

이를 정수로 표현하면 ~x = -(x+1)의 값이 나옵니다.

 

LEFT SHIFT <<

 

2 << 2 # 8    

# 0b10 -> 0b1000
# 2^1 * 2^2 = 2^3

 

LEFT SHIFT 연산자는 이진수로 보았을 때, 왼쪽으로 한 칸 이동시킵니다.

이는 정수로 보았을 때, 2의 거듭제곱만큼 곱하는 것과 같습니다.

 

RIGHT SHIFT >>

 

8 >> 2 # 2    

# 0b1000 -> 0b10
# 2^3 / 2^2 = 2^1

 

RIGHT SHIFT 연산자는 이진수로 보았을 때, 오른쪽으로 한 칸 이동시킵니다.

이는 정수로 보았을 때, 2의 거듭제곱만큼 나누는 것과 같습니다.

 

비트 마스킹을 이용한 집합 표현

비트마스킹을 이용하면, 이진수를 통해 집합 자료형을 만들 수 있습니다.

 

집합

 

0과 자연수를 성분으로 갖는 집합을 표현해보겠습니다.

0을 없음, 1을 포함으로 나타냅니다.

이진수의 인덱스(idx)가 0부터 시작한다고 할 때, 집합 {1, 2, 3}은 다음과 같이 나타낼 수 있습니다.

 

0b1110 # {3, 2, 1} 0은 없음

 

합집합

 

합집합은 OR 연산자를 통해 나타낼 수 있습니다.

 

0b1010 | 0b0100 = 0b111 # {3, 1} U {2} = {3, 2, 1}

 

교집합

 

교집합은 AND 연산자를 통해 나타낼 수 있습니다.

 

0b1110 & 0b0100 = 0b0100 # {3, 2, 1} ∩ {2} = {2}

 

여집합

 

여집합은 NOT 연산자를 통해 나타낼 수 있습니다.

(전체 집합은 이진수의 길이를 기준으로 잡아집니다)

 

~0b1100 # {3, 2}c = {1, 0}

 

차집합

 

A의 차집합은 B의 여집합과의 교집합을 통해 나타낼 수 있습니다.

 

0b1100 & ~0b0110 = 0b # {3, 2} - {2, 1} = {3}

 

성분 추가

 

성분을 추가하기 위해서는 해당 idx를 1로 바꾸어주어야합니다.

예를 들어 7를 추가하기 위해서는 이진수의 7번째 idx를 1로 바꾸어주어야합니다.

이는 합집합을 통해 구현할 수 있습니다.

 

0b1110 | 0b10000000 = 0b10001110 # {3, 2, 1} U {7} = {7, 3, 2, 1}

 

7번째 idx에 1이 있는 것은 LEFT SHIFT 연산을 통해 구현할 수 있습니다.

 

1 << 7 # 0b10000000

 

성분 삭제

 

성분을 삭제하기 위해서는 해당 idx를 0으로 바꾸어주어야합니다.

예를 들어, 7을 삭제하기 위해서는 이진수의 7번째 idx를 0으로 바꾸고, 동시에 나머지 idx는 그 값은 유지해야합니다.

이는 기존 집합에서 7을 제외한 전체 집합의 모든 원소를 포함하는 집합을 빼는 차집합으로 표현할 수 있습니다.

이를 코드로 교집합과 NOT을 통해 구현할 수 있습니다.

 

0b10001110 & ~0b10000000
= 0b10001110 & 0b01111111 = 0b1110 # {7, 3, 2, 1} - {7} = {3, 2, 1}

 

 

성분 조회

 

성분을 조회하기 위해서는 해당 idx만을 추출해 1인지 판별할 수 있으면 됩니다.

예를 들어 7이 있는지 확인하기 위해서는 7번째 idx만 1인 이진수를 만든 후에

교집합을 통해 원래 이진수의 7번째 idx를 추출하면 됩니다.

만약 해당 idx가 0이라면, 모든 숫자가 0이라 0이 됩니다. 즉, 결과값이 0이 아님을 비교함을 통해 조회할 수 있습니다.

 

0b10001110 & (1 << 7) != 0

 

성분 토글

 

토글 연산은 성분이 있으면 제거하고, 없으면 추가하는 연산입니다.

이는 XOR 연산을 통해 구현할 수 있습니다.

 

0b10001110 ^ (1 << 7) = 0b00001110 # 7 제거
0b00001110 ^ (1 << 7) = 0b10001110 # 7 추가

 

길이 조회

 

집합의 길이는 이진수 내의 1의 개수과 같습니다.

파이써넹서 이진수는 정수로 계산할 수 있으므로 2로 나누는 것을 반복하며 나머지를 전부 더합니다.

 

def lengthSet(binary):
	if binary == 0: return 0
    return binary % 2 + lengthSet(binary // 2)

 

공집합

 

공집합은 정수 0을 통해 구현할 수 있습니다.

0b0 = 0이기 때문입니다.

 

empty_set = 0

 

n개의 원소가 모두 들어있는 집합

 

0부터 7까지의 원소가 모두 들어있는 집합은 LEFT SHIFT 연산자로 1을 8만큼 이동한 후 1을 빼면 만들 수 있습니다.

 

(1 << 8) - 1
= 0b100000000 - 1
= 0b11111111

 

 

Reference

[Python] 비트 마스킹 정리