[Python] 비트연산자

컴퓨터는 어떤 데이터를 저장하더라도 비트 구조로 변환해 데이터를 저장하게 되어 있고,

저장된 비트는 다시 적절한 형태로 변환되어 사용된다.

 

이러한 변환 작업없이 비트형태를 그대로연산에 적용하는 것이 비트연산자이다.

비트 : 2진수(binary digit)의 줄임말
비트 연산 : 2진수의 연산

 

1. 시프트 연산자

  1-1) 왼쪽 시프트 연산자 (<<)

  : 각 비트를 왼쪽으로 옮긴다.

  : 2^n을 곱하는 효과

print(bin(8)) #8의 2진수 : 0b1000
print(8<<2) #8*4 = 32

 

  1-2) 오른쪽 시프트 연산자(>>)

  : 각 비트를 오른쪽으로 옮긴다 (오른쪽부터 값이 버려짐)

  : 2^n으로 나누는 효과

print(bin(8)) #8의 2진수 : 0b1000
print(8>>1) #8/2 = 4

 

2. AND 연산자 (&)

: 각 자리수를 비교해 둘 다 1이면 1, 아니면 0

 

3. OR 연산자 (|)

: 각 자리수를 비교해 둘 중 하나만 1이면 1

 

4. XOR 연산자 (^)

: 각 자리수를 비교해 다르면 1, 같으면 0

 

5. NOT 연산자 (~)

: 1은 0으로, 0은 1으로 변환

: NOT 연산자 수행시 -(입력값+1)의 결과값 리턴

 

 

*알고리즘 활용

 

1. 1부터 2^63이하의 임의의 수를 입력 받고, 그 수가 2의 제곱수에 해당하는지 판단하시오.

*2의 제곱수 확인 방법

: num에서 1을 뺸 2진수를 NOT 연산을 시킨 2진수와 num을 AND 연산했을 때 num이 나오면 2의 제곱수

num = 1073741824
if num == num & ~(num -1):
	print("2의 제곱수입니다.")
else:
	print("2의 제곱수가 아닙니다.")

 

2. 좌표축과 평행한 직사각형엔 4개의 점이 있습니다. 이 중 하나의 점(p)의 좌표가 비공개되어 있을 때,

나머지 3개의 점(a,b,c)의 좌표를 이용해 점(p)의 좌표를 구하는 프로그램을 개발하세요.

*같은 수를 연산하여 없앨 수 있는 XOR 연산자 활용

: 같은 수 2개와 다른 수 1개를 XOR 연산하면 같은 수는 0이 되고 다른 수 1개만 남음

: 점 p의 좌표는 a,b,c 중 하나의 x좌표와 y좌표로 이루어질것이므로 XOR 연산자를 사용하여 해결 가능

a = [3,4]
b = [12,4]
c = [3,8]

p=[]

p[0] = a[0] ^ b[0] ^ c[0]
p[1] = a[1] ^ b[1] ^ c[1]

 

3. 부분집합 생성

(ex. 배열의 길이가 3인 경우)

: 부분집합의 수는 2^3개 (각 원소가 있거나 없거나 2가지의 경우를 가지므로)

: 부분집합의 모든 경우의 수는 이진수로 표현 가능

  (000, 001, 010, ... 111)

: 주어진 배열 내 원소에 해당하는 자리수의 위치도 이진수로 표현 가능하고 이는 시프트연산으로 표현 가능

 (001, 010, 100) = (1<<0, 1<<1, 1<<2)

: 따라서 배열 내 원소의 인덱스값과 부분집합의 경우의 수를 &연산하였을 때 0이 아니면 해당 원소가 부분집합에 포함된다.

십진수	이진수	[3,6,7]
0	000	[]
1	001	[3]
2	010	[6]
3	011	[3,6]
4	100	[7]
5	101	[3,7]
6	110	[6,7]
7	111	[3,6,7]

 

arr = [3,6,7]
n = len(arr)
subList = []
 
for i in range(1<<n): #000 ~ 111까지 모든 경우 확인
	subset = []
    for j in range(n): #각 인덱스마다 해당 원소가 이번 부분집합에 들어갈지 말지 확인
        if i & (1<<j):
        	subset.append(arr[j])
    subList.append(subset)
 print(subList) #[[], [3], [6], [7], [3,6], [3,7], [6,7], [3,6,7]]

 

 

 

*참고

https://velog.io/@94applekoo/%EB%B9%84%ED%8A%B8%EC%97%B0%EC%82%B0%EC%9E%90%EB%A1%9C-%EB%B6%80%EB%B6%84-%EC%A7%91%ED%95%A9%EC%9D%84-%EC%83%9D%EC%84%B1%ED%95%98%EB%8A%94-%EB%B2%95-python

Today I Learned 32 - 알고리즘 / 비트연산자로 부분 집합을 생성하는 법 (python)

https://inuplace.tistory.com/224

[알고리즘] 비트연산자를 활용하여 부분집합 만들기

https://hoho325.tistory.com/235