비트 연산자 완전 정복!

mj·2024년 8월 11일

GSC신촌 교보DTS 글로벌소프트웨어캠퍼스 내맘대로TIL챌린지 클라우드교육

CDA

목록 보기

3/18

호텔을 운영 중인 A씨가 호텔 방들의 예약 여부를 표현하고 싶다고 할 때, 어떤 방법을 쓰는 게 좋을지 6개의 step으로 나누어 보도록 하자.

Step 1: list를 이용한 flag 처리

4개의 호텔방을 flag라는 리스트로 표현해보자.
방이 예약되어 있다면 1, 비어 있다면 0으로 표기한다.

### step 1 ###
# list을 이용한 flag 처리

# 4개의 방
flag = [0,0,0,0]

# 0번, 3번 방 예약 처리
flag[0] = 1
flag[3] = 1

print("현재 예약되어 있는 방은 ", end = "")
for i in range(len(flag)):
    if flag[i]:
        print(f"{i}번", end = " ")
print("방입니다.\n")

# 3번 방 비우기
flag[3] = 0

print("현재 예약되어 있는 방은 ", end = "")
for i in range(len(flag)):
    if flag[i]:
        print(f"{i}번", end = " ")
print("방입니다.")

리스트를 사용하면 이해하기는 쉽지만 메모리를 많이 사용해야 한다는 단점이 있다.
A씨가 필요한 정보는 방이 예약되어 있는지 / 아닌지 2개밖에 없는데, 이것을 정수형으로 표현했기 때문에 4byte씩이나 필요한 것이다.

A씨는 메모리 효율을 비해 비트 연산자를 이용해 표현하기로 했다.

Step 2: 비트 연산자를 활용한 flag 처리

우선 step 2에서는 다음의 4개의 비트 연산자를 사용한다.

x & y : AND 연산 (두 개의 비트가 모두 1일 때 1을 반환)
x | y : OR 연산 (두 개의 비트 중 하나라도 1이면 1을 반환)
x ^ y : XOR 연산 (두 개의 비트가 서로 다른 경우에 1을 반환)
~x : NOT 연산 (비트를 0에서 1로, 1에서 0으로 반전)

### step 2 ###
# 비트 연산자를 활용한 flag 처리

flag = 0

# 0번방 예약 처리 (1 -> 0001)
flag |= 1

# 3번방 예약 처리 (8 -> 1000)
flag |= 8

print("현재 예약되어 있는 방은 ", end = "")
for i in range(len(bin(flag))-2):
    if (flag & (1<<i)):
        print(f"{i}번", end = " ")
print("방입니다.\n")

# 3번방 방 비우기
flag &= ~8

print("현재 예약되어 있는 방은 ", end = "")
for i in range(len(bin(flag))-2):
    if (flag & (1<<i)):
        print(f"{i}번", end = " ")
print("방입니다.")

코드에서 flag |= 1은 flag = flag | 1와 같고, flag |= 8은 flag = flag | 8와 같다.

flag |= 1: 0번방 예약
flag |= 8: 3번방 예약
flag = 1001이므로 예약이 잘 되었다!

NOT 연산자를 이용해 3번방을 비우는 연산이다.
1000을 NOT 연산자로 0111으로 바꾸면 3번방만 0인 상태가 된다. 이것을 기존의 flag와 AND 연산하면 3번방만 빠지게 된다.
그러면 최종적으로 flag는 0번방만 예약되어 있는 상태인 0001이 된다.

❓ for문에서 사용한 len(bin(flag))-2가 뭘까?
bin() 함수는 10진수 숫자를 2진수 문자열로 바꿔주는 함수이다.
bin(10)
>>> '0b1010'
바꿔줄 때 앞에 0b가 붙기 때문에 (문자열 길이 - 2)를 해줘야 변환한 2진수의 실제 길이를 구할 수 있다.

❓ 그럼 if (flag & (1<<i))는?
step 3에 나오는 시프트 연산자를 사용하기 때문에 step 3에서 설명 예정 🤓!

비트 연산자를 이용해서 메모리 효율이 이전보다는 좋았지만 0번방을 1, 3번방을 8로 표현하니까 가독성이 좋지 않다는 단점이 있었다.
가독성을 해결하기 위해 시프트 연산자를 이용해보도록 하자.

Step 3. shift 연산자를 사용해 가독성을 높이기

시프트 연산자(shift 연산자)

<<: 비트를 왼쪽으로 이동
>>: 비트를 오른쪽으로 이동

num<<n은 $num\times2^n$ 와 같다.
num>>n은 $num/2^n$ 와 같다.

### step 3 ###
# shift 연산자를 사용한 가독성을 높이자

flag = 0

# 0번방 예약 처리
flag |= 1<<0

# 3번방 예약 처리
flag |= 1<<3

print("현재 예약되어 있는 방은 ", end = "")
for i in range(len(bin(flag))-2):
    if(flag & (1<<i)):
        print(f"{i}번", end = " ")
print("방입니다.\n")

# 3번방 비우기
flag &= ~(1<<3)

print("현재 예약되어 있는 방은 ", end = "")
for i in range(len(bin(flag))-2): 
    if (flag & (1<<i)):
        print(f"{i}번", end = " ")
print("방입니다.\n")

step 2에서의 코드와 크게 달라진 점은 없고 flag를 시프트 연산자를 이용해서 표현하여 코드의 가독성을 높였다.

step3에서의 1<<0, 1<<3을 자세히 설명하면 다음과 같다.

그럼 이제 예약되어 있는 방을 출력하는 for문 안의 if (flag & (1<<i))를 설명할 수 있게 되었다 😚
1<<i는 i번방을 의미하는 2진수이고 flag와 AND 연산을 하면서 if i번방이 예약되어 있다면을 의미하게 된다.

Step 4: 1000개의 아이템 사용하기

호텔에 4개의 방만 있을 수는 없으니 이번에는 1000개의 방이 있다고 가정해보자.

flag를 1000개의 요소를 가진 리스트로 사용하는 것은 매우 비효율적인 방법이니, 16개의 요소를 가진 리스트로 만들고 인덱스 하나가 64개의 방을 맡는 방법을 사용해보자. (16 * 64 = 1024이기 때문에 1000개의 방을 모두 관리할 수 있다.)

표로 표현하면 다음과 같다.

예를 들어 800번 방은 12번 인덱스에서 관리하는 것이다.

330번, 845번 방을 예약했다가 845번 방을 비우는 코드를 작성해보자.

### step 4 ###
# 1000개의 아이템 사용하기

flag = []

# flag = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for i in range(16):
    flag.append(0)

# 330번 방, 846번 방 예약 처리
flag[(330//64)] |= (1 <<(330 % 64)) 
flag[(846//64)] |= (1 <<(846 % 64)) 

print(f"@@@ 현재 flag = {flag}\n")

print("현재 예약되어 있는 방은 ", end = "")
for i in range(len(flag) * 64):     # len(flag) * 64 = 1024
    if ((flag[i//64] & (1<<(i%64)))):
        print(f"{i}번",end=' ')       
print("방입니다.\n")

# 845번 방 비우기
flag[(846//64)] &= ~(1<<(846%64))

print("현재 예약되어 있는 방은 ", end = "")
for i in range(len(flag) * 64):
    if (flag[i//64] & (1<<(i %64))):
        print(f"{i}번",end=' ')
print("방입니다.")

이전과는 달리 방의 개수가 늘어났으니 몫 연산과 나머지 연산을 사용하였다.

예약 처리부터 하나씩 코드를 뜯어보도록 하자. 🤔

# 330번 방, 846번 방 예약 처리
flag[(330//64)] |= (1 <<(330 % 64))
flag[(846//64)] |= (1 <<(846 % 64))

num번 방을 예약 처리하는 코드는 다음의 과정을 따른다.

예약하고 싶은 방을 담당하고 있는 인덱스를 num//64를 이용해서 찾는다.
해당 인덱스에 1<<(num\%64)을 OR 연산한다.

몫 연산과 나머지 연산을 하고 나면 다음 코드로 이해할 수 있다.

flag[5] = flag[5] | (1<<10)
flag[13] = flag[13] | (1<<14)

330번을 담당하고 있는 5번 인덱스에 $2^{10}$ 을 저장하고, 846번을 담당하고 있는 13번 인덱스에 $2^{14}$ 을 저장한다.

저장된 값은 출력한 결과에서 확인할 수 있었다.

다음은 현재 예약되어 있는 방을 출력하는 코드이다.

print("현재 예약되어 있는 방은 ", end = "")
for i in range(len(flag) * 64):
    if (flag[i//64] & (1<<(i%64))):
        print(f"{i}번",end=' ')       
print("방입니다.\n")

len(flag) * 64은 1024이기 때문에 예약된 방을 찾기 위해 for문 1024번 돈다. (물론 우리가 넣을 값은 1000까지이기 때문에 사실 나머지 24번은 쓸모 없는 반복이긴 하다)

flag[i//64]: flag의 인덱스 안에 들어가있는 요소
1<<(i%64): 인덱스 안에 들어갈 수 있는 값

예를 들어 i=320, 321, 330인 경우를 살펴보자.
(현재 5번 인덱스에 1024, 13번 인덱스에 16384가 저장되어 있음)

이렇게 i가 증가할수록 1, 10, 100, 1000 ... 규칙으로 수가 변해간다.

호텔 예약을 한 i=330인 경우도 살펴보자.

& 연산의 결과가 True가 되어서 if 조건문을 만족하여 방 번호를 출력하게 된다.

다음은 846번 방을 비우는 코드이다.

# 846번 방 비우기
flag[(846//64)] &= ~(1<<(846 % 64))

마찬가지로 몫 연산과 나머지 연산까지 하면 다음의 코드로 이해할 수 있다.

flag[13] = flag[13] & ~(1<<14)
# ~(1<<14) = ~(100000000000000) = 011111111111111

연산을 끝내면 깔끔하게 flag[13] 인덱스 안의 14번째 방을 비울 수 있다.

❓ 그런데 어차피 & 연산을 할거면 뒷부분을 ~(1<<14)가 아니라 0으로 하면 간편하지 않나? 라는 의문이 들 수도 있다.
❗이 예시에서는 인덱스 하나당 하나의 방만 예약된 경우지만, 하나의 인덱스에 두 개 이상의 방이 예약된 경우를 한 번 살펴보자.
# 330번 방, 846, 847번 방 예약 처리
flag[(330//64)] |= (1 <<(330 % 64)) 
flag[(846//64)] |= (1 <<(846 % 64)) 
flag[(847//64)] |= (1 <<(847 % 64)) 
(이 경우, 13번 인덱스에 1100000000000000가 저장된다.)
만약 flag[(846//64)] &= 0를 실행한다면 인덱스의 요소가 아예 0이 되어 846, 847이 전부 날라가게 된다.

Step 5: 함수를 이용한 모듈화

코드 구성은 다 되었지만 어쩐지 코드가 복잡해 보인다.
함수를 만들어 코드를 좀 더 알아보기 쉽게 바꿔보자.

bit_set(): 예약 처리
bit_clr(): 퇴실
bit_isset(): 예약 되어 있는지 확인
print_set(): 예약된 방 출력

### step 5 ###
# 함수를 이용한 모듈화

# 예약 처리
def bit_set(index):
    flag[(index//64)] |= ( 1 << (index %64))

# 퇴실
def bit_clr(index):
    flag[(index//64)] &= ~(1<<(index % 64))

# 방이 예약되어 있는지 확인
def bit_isset(flag, index):
    return flag[index//64] & (1<<(index %64))
    
# 예약된 방 출력
def print_set(flag):
    print("현재 예약되어 있는 방은 ", end = "")
    for i in range(len(flag) * 64):
        if (bit_isset(flag, i)):
            print(f"{i}번", end=' ')
    print("방입니다.\n")

flag = []

for i in range(16):
    flag.append(0)

# 330, 846번 방 예약 처리    
bit_set(330)
bit_set(846)

# 현재 예약되어 있는 방 출력
print_set(flag)
    
# 846번 방 비우기
bit_clr(846)

# 현재 예약되어 있는 방 출력
print_set(flag)

Step 6: 루틴 테스트

main() 함수를 만들어 여러 개의 방을 예약하고, 퇴실하는 것까지 해보자.

### step 7 ###
# 루틴 테스트
# main() 함수 만들기
def bit_set(flag,index):
    flag[(index//64)] |= ( 1 << (index %64))
    
def bit_clr(flag,index):
    flag[(index//64)] &= ~(1<<(index % 64))
    
def bit_isset(flag,index):
    return flag[index//64] & (1<<(index %64))
    
def print_set(flag):
    print("현재 예약되어 있는 방은 ", end = "")
    for i in range(len(flag) * 64):
        if (bit_isset(flag, i)):
            print(f"{i}번", end=' ')
    print("방입니다.")

def BIT():
    flag = []
    for i in range(16):
        flag.append(0)
    return flag
    
#--------------------------------------------------------------
def main():
    flag = BIT()
    
    bit_set(flag, 700)
    bit_set(flag, 800)
    
    print_set(flag)

    # ---        
    print('-' * 50)
    
    bit_set(flag, 100)
    bit_set(flag, 200)
    
    print_set(flag)

    # ---
    print('-' * 50)
    
    bit_clr(flag, 200)
    bit_clr(flag, 700)
    
    print_set(flag)
	
     # ---
    print('-' * 50)
    
main()