[Python] 비트 연산자

 

비트 연산자

비트 연산자		a = 0b1010, b = 0b0100
&	AND	a & b -> 0b0000
|	OR	a | b -> 0b1110
^	XOR	a ^ b -> 0b1110
~	NOT	~a -> 0b0101
<<	왼쪽 Shift	a << n -> a * 2^n
>>	오른쪽 Shift	a >> n -> a * 2^-n

 

 

비트 연산자 응용

나누기, 나머지 연산

흔히 쓰이는 /, % 연산자는 오버헤드가 크기 때문에 필요한 경우 더 빠른 비트 연산을 사용할 수 있다.

 

나누는 수가 2^n인 경우 >> 연산자가 / 연산자를 대체할 수 있다.

ex) 9 / 8 = 1 -> 9 >> 3 = 1

 

나누는 수가 2^n인 경우 & 연산자를 활용해 % 연산자를 대체할 수 있다.

2^n 꼴의 숫자를 이진수로 표현하면 최상위 비트만 1인 형태를 띄게 되고, 2^n에 -1을 더하면 n-1번 이하의 모든 bit들이 1로 변하는 것을 이용하면 된다.

ex) 9 % 4 = 1 -> 9 & 3 = 1

 

이를 홀수 판별에도 적용할 수 있다.

n % 2 = n & 1

 

SWAP

XOR 연산을 사용하면 임시 변수를 선언하지 않고 두 변수의 값을 바꿀 수 있다.

a = 10 
b = 30
a ^= b
b ^= a
a ^= b

 

비트마스킹

각 bit를 하나의 flag로 활용한다면 자료 저장과 집합 표현을 쉽게 할 수 있다.

ex) 사람에 0~31 사이의 번호가 매겨져 있고, 사람 A의 친구 목록이 {0, 3, 6, 7, 10, 13, 28}이고, B의 친구 목록이 {0, 1, 4, 5, 6, 17, 21, 28} 이라고 하자.

이 때 다음 과 같은 문제를 푼다면?

1. A 또는 B가 아는 친구의 수는?

2. A와 B 사이에 겹치는 친구의 수는?

반복문을 이용해서 문제를 풀 수도 있지만 비트를 사용하면 이러한 '집합' 여산이 간단해진다.

친구 목록을 사람 번호로 저장하지 않고 x번째 사람이 내 친구라면, x번째 비트를 1로 표시하는 방식을 사용해보자.

 

그러면 A의 친구 목록은 전체 사람의 수가 32명이므로 32bit 이진수에 0, 3, 6, 7번 비트를 1로 표시한

0001 0000 0000 0000 0010 0100 1100 1001 이 된다.

B의 친구도 이와 같이 바꾸면

0001 0000 0100 0010 0000 0000 0111 0011 이 된다.

 

1번 문제는 두 친구 목록을 | 연산해 구할 수 있고, 2번 문제는 & 연산해 구할 수 있다.

 

+) i & (1 << j)

i의 j번째 비트가 1인지 아닌지를 의미한다.