[CS] 비트연산(Bit Operation)

비트마스크?

정수를 이진수로 표현하여 비트 연산을 통해 빠른 연산을 하는 테크닉입니다.

특정 방문 여부를 확인하는 1차원 배열을 간단한 정수로 나타낼 수 있어 빠른 연산과 적은 용량으로 방문여부를 확인할 수 있습니다. DP를 공부하면서 제대로 접하였습니다.

# 1차원 배열
a = [1, 1, 0, 0, 1, 0, 1, 0]

# 비트마스크
a = 0b11001010 = bin(202)

정수의 용량?

대부분의 언어 및 64비트 운영체제에서는 정수형에 4byte를 할당한다고 합니다.

4yte = 32bit (8bit * 4)

정수형은 32개의 0과 1이 들어갈 수 있는 공간을 가집니다. 맨 앞 공간은 부호를 위한 공간으로 활용되어 수를 나타내는 bit는 31개가 되어 $-2^{31}$ 부터 $2^{31}-1$까지의 숫자를 나타낼 수 있습니다.

논리 연산자

논리 연산자를 통해 비트를 조작할 수 있습니다. 논리연산자에서는 AND(&), OR(|), XOR(^), NOT(~) 등이 있습니다. 파이썬 코드를 기준으로 작성하겠습니다.

AND 연산(&)

1과 1을 AND 연산하면 1을 반환합니다. 이외에는 모두 0을 반환합니다.

# 1 & 1 = 1
# 1 & 0 = 0   /   0 & 1 = 0   /   0 & 0 = 0

bin(0b1010 & 0b1100) = 0b1000
10 & 12              = 8

OR 연산(|)

어떠한 수와 1을 OR 연산하면 1을 반환합니다. 0과 0을 OR 연산 할때만 0을 반환합니다.

# 1 | 1 = 1   /   1 | 0 = 1   /   0 | 1 = 1
# 0 | 0 = 0

bin(0b1010 | 0b1100) = 0b1110
10 | 12              = 14

XOR 연산(^)

서로 같은 비트값을 XOR 연산하면 0을, 다른 비트값을 XOR 연산하면 1을 반환합니다.

# 1 ^ 0 = 1   /   0 ^ 1 = 1
# 0 ^ 0 = 0   /   1 ^ 1 = 0

bin(0b1010 ^ 0b1100) = 0b0110
10 ^ 12              = 6

NOT 연산(~)

0을 NOT 연산하면 1을, 1을 NOT 연산하면 0을 반환합니다.

하지만 파이썬에서 보여지는 과정은 조금 다릅니다. 해당 과정은 1의 보수를 구하는 과정이고 파이썬 비트연산의 NOT은 2의 보수를 취하여 음수화 한다고 합니다. 양의 정수에 부호를 붙인 뒤 -1을 더하는 과정입니다. 예를들면 13을 NOT 연산하면 -14가 되는 식입니다. 파이썬에서 1의 보수값이 필요하다면 XOR 연산을 이용해야 합니다.

# 2의 보수
bin(~0b1010) = -0b1011
~10          = -11

# 1의 보수
bin(0b1010 ^ 0b1111) = 0b0101

시프트 연산자

SHIFT 연산(<<, >>)

비트연산의 핵심 연산자입니다.

왼쪽 쉬프트 연산 a << b는 a의 비트값을 왼쪽에 0을 채우면 왼쪽으로 b칸만큼 밀어냅니다. 왼쪽 쉬프트 연산은 n * 2와 같은 결과를 보여줍니다.

오른쪽 쉬프트 연산 a >> b는 a의 비트값을 오른쪽 비트값을 삭제하면서 오른쪽으로 b칸만큼 밀어냅니다. 오른쪽 쉬프트 연산은 n // 2와 같은 결과를 보여줍니다.

# Left Shift
bin(0b1010 << 2) = 0b101000
10 << 1          = 20
10 << 2          = 40

# Right Shift
bin(0b1100 >> 2) = 0b11
12 >> 1          = 6
13 >> 1          = 6

가장 왼쪽의 비트만 1인 네 자리 비트 값을 만들고 싶다면 시프트 연산을 사용합니다. 아래 활용 부분에서 자주 사용하게 됩니다.

bin(1 << 4) = 0b1000

연산자 활용

N번째 비트 조회

1 << N과 비교할 비트값과 AND 연산을 수행하여 값을 확인합니다. 조회하는 비트값이 1이라면 원본(1000)을 반환하고, 조회하는 비트값이 0이라면 0을 반환합니다.

N = 3
bin(0b1010 & (1 << N)) = 0b1000
bin(0b0010 & (1 << N)) = 0b0

N번째 비트 추가

1 << N과 비교할 비트값을 OR 연산해줍니다. 원본에서 추가할 부분이 어떤 비트이던 1로 수정됩니다.

N = 3
bin(0b0010 | (1 << N)) = 0b1010

N번째 비트 제거

1 << N을 NOT 연산한 후 비교할 비트값과 AND 연산해줍니다. 원본에서 추가할 부분이 어떤 비트이던 1로 수정됩니다.

N = 3
bin(0b1010 & ~(1 << N)) = 0b0010

N번째 비트 토글

1 << N과 비교할 비트값을 XOR 연산해줍니다. 원본에서 토글할 비트값이 0이면 1로, 1이면 0으로 바뀝니다.

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

모든 비트가 1인 N개의 비트값 만들기

1 << N에서 1을 빼주면 N개의 비트가 모두 1인 비트값을 만들 수 있습니다.

N = 3
bin((1 << N) - 1) = 0b1111

N번째 값부터 왼쪽 모든비트 제거

(1 << N) - 1과 비교할 비트값을 AND 연산해줍니다. (1 << N) - 1는 N번째 전까지만 1의 비트값을 가지기 때문에 AND 연산을 하면 N번째 전의 값만 남게됩니다.

N = 3
bin(0b11001100 & ((1 << N) - 1)) = 0b00000100

N번째 값부터 오른쪽 모든비트 제거

-1 << (N + 1)과 비교할 비트값을 AND 연산해줍니다.

모든 비트값이 채워진 값은 -1입니다. -1을 왼쪽 시프트 하게되면 ...1111000과 같은 값이 만들어 지게 되고, 0과 AND연산 되는 부분이 삭제되는 원리입니다.

N = 3
bin(0b11001100 & (-1 << (N + 1))) = 0b11000000