수학 알고리즘: 비트 연산자

들어가면서

저번 글에서 2진수를 표현하는 함수에 대해서 알아보았다.

파이썬 내장함수 이용하기
	value = 60

	b1 = bin(value)		#0b111100
	o1 = oct(value)		#0o74
	h1 = hex(value)		#0x3c

비트 연산자

비트 연산자는 두 개의 이진수로 이루어진 표현식에 사용하는 연산자이다.

파이썬의 표현식은 평가가 가능한 "수식"을 뜻한다.

비트가 무엇인지?
0과 1 (on 과 off)만 표현할 수 있다.

따라서 비트 연산자도 0과 1에 대해서 연산을 수행한다.

비트 연산자의 종류

연산자	기능	문법	설명
&	비트 AND	a & b	a와 b의 비트를 AND 연산
|	비트 OR	a | b	a와 b의 비트를 OR 연산
^	비트 XOR	a ^ b	a와 b의 비트를 XOR 연산(배타적 OR, Exclusive OR)
~	비트 NOT	~x	x의 비트를 뒤집음
<<	비트 왼쪽 시프트	a << b	a의 비트를 b번 왼쪽으로 이동시킴
>>	비트 오른쪽 시프트	a >> b	a의 비트를 b번 오른쪽으로 이동시킴

사용 예시

& 비트 and 연산자

특정 위치의 비트를 출력하고 싶을 때 사용한다.
ex) ??? & 00001111 ➡️ 하위4비트의 값이 출력된다.

bin_num = 0b01110111

print(format(bin_num&11110000,'#b'))    #0b1110000

왼쪽 시프트는 *2연산을 수행한다.

x1 = 3

# x1를 2배하고 싶다.
print(x1<<1)    #6

# x1를 2^n하고 싶다. (2배는 2^1)
print(x1<<2)    #4배 12
print(x1<<3)    #8배 24
print(x1<<4)    #16배 48

오른쪽 시프트는 2^n로 나눈 것의 정수몫이다.

x2 = 48

# x2를 /2하고 싶다.
print(x2>>1)    #24

# x1를 2^-n하고 싶다. *정수몫
print(x2>>2)    #12
print(x2>>3)    #6
print(x2>>4)    #3
print(x2>>5)    #1 (2^5 = 32 , 48//32 = 1
print(x2>>6)    #0 (2^5 =  64, 48//64 = 0

알고리즘에서의 비트 연산자

특히 코딩테스트에서 유용하게 사용할 수 있는 비트 연산자의 쓰임새를 소개하겠다!

짝수, 홀수 판별

짝수는 이진수로 표현했을 때 마지막 자리가 늘 0이다.
홀수는 반대로 0이다.
따라서 1과 &연산시 홀수는 1을, 짝수는 0을 출력한다.

x3 = 3
x4 = 4

print(x3 & 1)   #홀수 1
print(x4 & 1)   #짝수 0

1<<n : n번째 비트 켜기

여기서 n번째는 0을 포함하는 숫자이다.

print(format(1<<4,"#b")) 	#0b10000

(1<<n) - 1 : n개의 비트 켜기

print(format((1<<4)-1,"#b"))    #0b1111

비트개수세기

2의 거듭제곱인지를 확인