[심화] 비트 연산을 통한 알고리즘의 최적화

비트 연산

비트란?

컴퓨터에서 자료를 표현하기 위해 사용하는 최소 단위로, 1bit = 0 or 1로 표현되고 8bit = 1byte이다.

 

비트 연산자

기본적인 비트 연산자는 &, |, ^, ~, <<, >> 등등이 있지만 여기서는 매우 기본적인 개념보다는 헷갈렸던 개념이나 연산의 쓰임새 등을 언급할 생각이다. 참고로 비트 연산자는 우선순위가 매우 낮은 편에 속하므로 헷갈리면 소괄호를 잘 활용하자.

 

a << n	a * $2^{n}$
a >> n	a * $2^{-n}$ (a / \(2^n\))

 

a << n은 왼쪽으로 n번 shift를 의미한다.
예로 1 << 2는 0001을 전체적으로 왼쪽으로 2번 이동하니 0100이 되고, 이는 10진수로 4를 의미한다. (1 * 4와 같다.)

a >> n은 오른쪽으로 n번 shift를 의미한다.
예로 4 >> 2는 0100을 전체적으로 오른쪽으로 2번 이동하니 0001이 되고, 이는 10진수로 1을 의미한다. (4 / 4와 같다.)

 

깊게 들어간다면 Arithmetic Shift와 Logical Shift가 있지만 일반적으로 사용할 때는 Logical Shift, 즉 자동적으로 0이 채워진다고 생각하면 무방하다.

 

이러한 비트 연산자로 숫자의 몇 번째 비트가 1인지 0인지를 판별할 수 있다.

 

i & (1 << j)는 i의 j번째 비트가 1인지 아닌지를 판별하는 코드다. (0이면 0을 반환하고 1이면 0이 아닌 수를 반환)
예를 들어 i가 0111이고 2번째 비트를 판별하고 싶다고 하자. 1은 0001이니 1 << 2는 0100이고 이를 i와 &연산해주면 0100이 나오니 0이 아닌 값을 리턴할 것이므로 정상적으로 판별이 가능하다.

 

아래 코드를 보자.

#include <iostream>
#include <bitset> 
// bitset 명령어를 사용하기 위한 헤더파일도 넣어준다.
// bitset(8)(i)는 i를 8비트로 출력하겠다는 의미이다. namespace를 쓰지 않으면 std::를 넣어야 한다.

using namespace std;

int main() {
    
    int i = 7; 

    cout << "i : " << bitset<4>(i) << "\n"; // 0111
    cout << "i의 0번째 비트 : " << (i & (1 << 0)) << "\n"; // 1
    cout << "i의 1번째 비트 : " << (i & (1 << 1)) << "\n"; // 2
    cout << "i의 2번째 비트 : " << (i & (1 << 2)) << "\n"; // 4
    cout << "i의 3번째 비트 : " << (i & (1 << 3)) << "\n"; // 0

    return 0;
}

만약 해당 비트가 0인지 1인지 정확히 출력하고 싶다면 (i & (1 << j)) >> j 코드를 사용하면 된다. 해석하면 그냥 좌Shift 한 만큼 다시 우Shift를 한다는 의미이다.

 

아래 코드를 보자.

#include <iostream>
#include <bitset> 
// bitset 명령어를 사용하기 위한 헤더파일도 넣어준다.
// bitset(8)(i)는 i를 8비트로 출력하겠다는 의미이다. namespace를 쓰지 않으면 std::를 넣어야 한다.

using namespace std;

int main() {

    int i = 7;

    cout << "i" << bitset<4>(i) << "\n"; // 0111
    cout << "i의 0번째 비트 : " << ((i & (1 << 0)) >> 0) << "\n"; // 1
    cout << "i의 1번째 비트 : " << ((i & (1 << 1)) >> 1) << "\n"; // 1
    cout << "i의 2번째 비트 : " << ((i & (1 << 2)) >> 2) << "\n"; // 1
    cout << "i의 3번째 비트 : " << ((i & (1 << 3)) >> 3) << "\n"; // 0

    return 0;
}

그 외에도 다양한 코드가 존재한다.

 

i & (1 << j)	i의 j번째 비트 판별
i | (1 << j)	i의 j번째 비트를 1로 변경
i & ~(1 << j)	i의 j번째 비트를 0으로 변경
i ^ (1 << j)	i의 j번째 비트를 반대로 변경

 

후에 언급할 비트 마스킹을 위해서는 3개의 명령어만 잘 숙지해둬도 무방할 듯 하다.

 

나누기, 나머지 연산

대부분 나누기나 나머지 연산을 할 때 /와 % 연산자를 사용하지만 더 빠른 비트 연산을 사용할 수도 있다.

 

• 나누는 수가 \(2^n\)인 경우  >> n으로 변경 가능
  

  #include <iostream>
  
  using namespace std;
  
  int main() {
  
      cout << 17 / 8 << "\n"; // 2
      cout << (17 >> 3) << "\n"; // 2 (8 -> 2^3)
  
      return 0;
  }

  
  
  
• 나누는 수가 \(2^n\)인 경우 & \(2^n\) - 1로 변경 가능
  \(2^n\)꼴의 숫자를 이진수로 표현하면 최상위 비트가 1로 표현된다. 또한 \(2^n\)에 -1을 더하면 n-1 이하의 모든 비트들이 1로 변하는 성질을 이용하면 된다.
  (4는 이진수로 100이고, -1을 더하면 3이 되는데 이는 이진수로 11이다.)
  

  #include <iostream>
  
  using namespace std;
  
  int main() {
  
      cout << 17 % 8 << "\n"; // 2
      cout << (17 & 7) << "\n"; // 2
  
      return 0;
  }

 

위치 바꾸기 (Swap)

^연산을 이용하여 임시 변수를 선언하지 않고 간단하게 swap을 구현할 수 있다. 간단하니 코드로 보자.

#include <iostream>

using namespace std;

int main() {
    int x = 3, y = 2;

    x ^= y; // x = x ^ y
    y ^= x; // y = y ^ x
    x ^= y; // x = x ^ y

    return 0;
}

 

비트마스킹 (Bit Masking)

발상의 전환을 활용한 테크닉이다. 13은 이진수 1101으로 표현 가능하다. 1101은 13으로 생각할 수 있지만, 이를 집합으로 생각해보자.

어떤 집합이 있다고 가정하자.

{0, 1, 2, 3, 4}, {1, 2, 4}, {2, 3}, {0, 4} .....

 

이러한 집합을 하나하나 배열로 표현하면 보기에는 쉽지만 많은 메모리를 차지하고 실행 시간도 늘어난다. 이를 해결하기 위해, 비트마스크를 활용한다. 비트의 각 자리를 집합의 유무 판단의 기준으로 생각하는 것이다. 즉

{0, 1, 2, 3, 4} -> 11111 => 31
{1, 2, 4} -> 10110 => 22
{2, 3} -> 01100 => 12
{0, 4} -> 10001 => 17

 

이런 식으로 부분집합을 배열이 아닌 정수 그대로 나타낼 수 있는 것이다. 집합을 조회하려면 앞서 보았던 i의 j번째 비트 판별 코드를 이용하면 편하다.

예를 들어 0부터 9까지의 배열을 만들어야 한다고 치자. 이를 배열로 만들지 않고 10자리의 비트를 가지고 있는 정수로 취급하면 11 1111 1111이 되었을 때, 즉 1023이 되었을 때 배열이 꽉 찼다고 할 수 있을 것이다. 비트를 수정할 때는 앞서 언급했던 코드를 사용하면 되니 훨씬 수월해진다.