[코드트리 챌린지] 5주차

---

실력진단 결과

코드트리 5주차 실력진단 결과

---

오늘의 학습

Bit Operator

다양한 비트 연산자에 대해 다뤄보도록 하겠습니다. 비트 연산은 기본적으로 2진법을 기반으로 합니다. Bit 연산는 컴퓨터의 기본 연산이기에 속도가 굉장히 빠릅니다.

 

1. and 연산자 (|)
   
   and 연산자 |는 두 수 a, b를 이진법으로 표현한 뒤 각 자리에 적혀있는 bit에 대해 and 연산을 진행한 후 그 결과를 다시 10진수로 표현해줍니다. and 연산이란 둘 다 1일 때만 1, 아니라면 0이 되는 연산입니다.
   
   예를 들어 5 | 6은 4가 됩니다.
   

              101     (5)
              110     (6)
   and  ----------
              100     (4)​

2. or 연산자 (|)
   
   or 연산자 |는 두 수 a, b를 이진법으로 표현한 뒤 각 자리에 적혀있는 bit에 대해 or 연산을 진행한 후 그 결과를 다시 10진수로 표현해줍니다. or 연산이란 둘 중 하나라도 1이라면 1, 아니라면 0이 되는 연산입니다.
   
   예를 들어 5 | 3은 7가 됩니다.
   

              101     (5)
              011     (3)
   or   ----------
              111     (7)​

3. xor 연산자 (^)
   
   xor 연산자 ^는 두 수 a, b를 이진법으로 표현한 뒤 각 자리에 적혀있는 bit에 대해 xor 연산을 진행한 후 그 결과를 다시 10진수로 표현해줍니다. xor 연산이란 두 bit가 다른 값이라면 1, 같은 값이라면 0이 되는 연산입니다. xor은 0또는 1 값만 갖는 x에 대해 x를 0<->1 이렇게 반전시켜주고 싶을 때 x = x^1 형태로 사용하기도 합니다.
   
   예를 들어 5 | 3은 6가 됩니다.
   

              101     (5)
              011     (3)
   xor  ----------
              110     (6)​

4. left shift 연산자 (<<)
   
   left shift 연산자 <<는 수 a를 이진법으로 표현한 뒤 모든 bit를 b번 왼쪽으로 밀어준 뒤 그 결과를 다시 10진수로 표현해줍니다.
   
   예를 들어 5 << 1은 10, 5 << 2는 20, 그리고 5 << 3은 40이 됩니다. 여기서 알 수 있는 재밌는 사실은 left shift를 한번 하면 값이 2배가 된다는 것입니다.
   

   5      = 0000101   (5)
   5 << 1 = 0001010   (10)
   5 << 2 = 0010100   (20)
   5 << 3 = 0101000   (40)​

5. right shift 연산자 (>>)
   
   right shift 연산자 >>는 수 a를 이진법으로 표현한 뒤 모든 bit를 b번 오른쪽으로 밀어준 뒤 그 결과를 다시 10진수로 표현해줍니다. 이때 더 이상 밀릴 곳이 없는 bit는 사라지게 됩니다.
   
   예를 들어 13 >> 1은 6, 13 >> 2는 3, 그리고 13 >> 3은 1이 됩니다. 여기서 알 수 있는 재밌는 사실은 right shift를 한번 하면 값이 2로 나눈 몫으로 바뀐다는 것입니다.
   

   13      = 0001101   (13)
   13 >> 1 = 0000110   (6)
   13 >> 2 = 0000011   (3)
   13 >> 3 = 0000001   (1)​

---

Bitmask

대부분의 프로그래밍 언어에서는 정수값을 표현하기 위해 4byte를 사용하고는 합니다. 1byte는 8bit이기에 정수 하나를 표현하기 위해 32개의 bit를 사용하게 됩니다. 만약 0부터 31까지의 수가 생기고 사라지는 것이 반복되는 문제가 주어졌다면 이는 크기가 32인 배열을 만들어 각 수들이 남아있는지에 대한 여부를 관리할 수 있습니다. 하지만 만약 0번부터 31번까지의 수가 존재하는지에 대한 여부를 0, 1에 해당하는 하나의 bit로서 관리한다고 생각해보면 32개의 bit로 표현이 되므로 이를 하나의 수 x로 표현할 수 있다는 뜻과 같습니다. 이를 Bitmask라 부릅니다.

편의상 수 0이 오른쪽에서부터 1번째 비트, 수 1는 오른쪽에서부터 2번째 비트, ..., 수 31은 오른쪽에서부터 32번째 비트로 나타냈다고 생각해보겠습니다. 그렇다면 각 상황에 대해서는 아래와 같이 하나의 수로 표현해볼 수 있을 것입니다.

                                    x         상황
00000000000000000000000000000000   (0) : 아무 수도 없는 경우
00000000000000000000000000001010  (10) : 1, 3만 있는 경우 
00000000000000000000000000100111  (39) : 0, 1, 2, 5만 있는 경우 
00000000000000000000000001000000  (64) : 6만 있는 경우

bitmask를 이용했기에 x값만 가지고 여러 연산을 진행할 수 있어야 합니다.

(1) 수가 존재하는지 여부 확인

현재 상태가 0, 1, 2, 5만 있는 경우라 아래와 같이 x는 39인 상황을 생각해보겠습니다.

00000000000000000000000000100111 (x = 39)

먼저 현재 수 2가 존재하는지를 x를 통해 알아보고자 합니다. 이는 간단하게 생각해서 x를 bit로 나타냈을 때 오른쪽에서 3번째 수가 1인지를 알아내면 됩니다.

이를 위해서 right shift 연산자를 이용하여 먼저 x를 오른쪽으로 2칸 밀어줍니다.

x              00000000000000000000000000100111 (39)
x >> 2         00000000000000000000000000001001 (9)

이제 가장 오른쪽 bit가 1인지를 확인하면 됩니다. 어떤 수가 주어졌을 때 가장 마지막 bit를 찾아내는 방법은 알아내기를 원하는 bit에만 1을 넣고 나머지에는 전부 0을 넣었을 때 나오는 값과 and 연산을 진행하는 것입니다. 여기서는 가장 오른쪽 bit만 알아내고 싶은 것이기에 1과 and 연산을 진행하면 끝 bit만 그대로 나오게 됩니다.

x              00000000000000000000000000100111 (39)
x >> 2         00000000000000000000000000001001 (9)
(x >> 2) & 1   00000000000000000000000000000001 (1)

만약 x가 0, 1, 5만 있는 경우라 아래와 같이 x는 35인 경우였다면, (x >> 2) & 1 결과는 0이 나오기에 수 2가 x에 존재하지 않는다는 것을 알 수 있게됩니다.

x              00000000000000000000000000100011 (35)
x >> 2         00000000000000000000000000001000 (8)
(x >> 2) & 1   00000000000000000000000000000000 (0)

따라서 수 k가 x에 존재하는지에 대한 여부는 (x >> k) & 1이 0인지 1인지로 판단이 가능합니다.

(2) 수를 새롭게 추가 / 삭제

현재 상태가 0, 1, 2, 5만 있는 경우라 아래와 같이 x는 39인 상황을 생각해보겠습니다.

00000000000000000000000000100111 (x = 39)

여기서 수 4를 새롭게 추가해보려고 합니다. 이를 위해서는 오른쪽에서 5번째 bit만 1인 수를 만든 뒤, 기존 x와 이 수를 더해주면 됩니다.

x              00000000000000000000000000100011 (35)
16             00000000000000000000000000010000 (16)
x + 16         00000000000000000000000000110011 (51)

생각해보면 수 4에 해당하는 가중치는 2^4입니다. 그 이유는 오른쪽에서 5번째 수를 1로 한 값이 새롭게 추가된 것이기 때문입니다. 2의 거듭제곱을 빠르게 얻을 수 있는 방법은 left shift를 이용해 1 << k 형태로 계산하는 것입니다. 처음 값 1을 시작으로 k번 왼쪽으로 bit를 밀어주면 2^k값을 바로 얻을 수 있게 됩니다. 여기서는 수 4에 해당하는 가중치를 구해야 하므로 (1 << 4)로 빠르게 해당하는 값 16을 얻을 수 있습니다.

x              00000000000000000000000000100011 (35)
1 << 4         00000000000000000000000000010000 (16)
x + (1 << 4)   00000000000000000000000000110011 (51)

즉, x + (1 << k) 형태로 수 k를 추가해줄 수 있습니다.

여기서 재밌는 사실은 or, xor 연산을 이용해도 동일한 결과가 나온다는 것입니다.

x              00000000000000000000000000100011 (35)
1 << 4         00000000000000000000000000010000 (16)
x + (1 << 4)   00000000000000000000000000110011 (51)
x | (1 << 4)   00000000000000000000000000110011 (51)
x ^ (1 << 4)   00000000000000000000000000110011 (51)

xor 연산의 경우 각 bit 중 0이 있는 위치에서는 x의 bit를 바꾸지 않고, 1이 있는 위치에서는 x의 bit를 바꿔주는 역할을 하기에 오른쪽에서 5번째 수를 1로 바꿔주게 된 것입니다.

이제 4가 추가되어 현재 상태가 0, 1, 2, 4, 5만 있는 경우라 x가 51이 된 상황에서 다시 4를 제거해보겠습니다. 이는 마찬가지 논리로 x - (1 << k)로 진행이 가능합니다.

x              00000000000000000000000000110011 (51)
1 << 4         00000000000000000000000000010000 (16)
x - (1 << 4)   00000000000000000000000000100011 (35)

여기서도 재밌는 사실은, xor을 이용해 이미 존재하는 4번째 수를 제거하는 것도 가능하다는 것입니다.

x              00000000000000000000000000110011 (51)
1 << 4         00000000000000000000000000010000 (16)
x - (1 << 4)   00000000000000000000000000100011 (35)
x ^ (1 << 4)   00000000000000000000000000100011 (35)

즉, x ^ (1 << k)는 수 k가 있다면 없애고, 없다면 새로 만들어주는 역할을 해주게 됩니다.

(3) 모든 수를 한번 다 채우기

모든 수가 다 채워져 있는 상태는 모든 bit가 1인 상태입니다. 만약 오른쪽에서 5개의 bit만 전부 1로 채우고 싶은 경우라면 (1 << 5) - 1이 바로 그러한 값이 됩니다. 그 이유는 6번째 bit에만 1을 채운 뒤 1을 빼주면 그 뒤에 있는 모든 비트를 1로 만들어 줄 수 있기 때문입니다.

(1 << 5) - 1   00000000000000000000000000011111 (31)

따라서 오른쪽 n개의 bit를 전부 1로 하는 값은 (1 << n) - 1로 한번에 계산이 가능합니다.