비트 연산과 비트 마스크

&와 |의 개념을 이해하고 있었지만, 문제에서 등장하면 바로바로 써먹지 못 하는 것 같아서 다시 정리해본다.

문제는 2018 KAKAO BLIND RECRUITMENT [1차] 비밀지도 를 풀었었다.

비트 연산과 비트 마스크를 활용하여 푼 결과는 다음과 같은데,

#include <string>
#include <vector>

using namespace std;

vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
    vector<string> answer;
    
    for (int i = 0; i < n; i++) {
        int map = arr1[i] | arr2[i];  // 두 배열의 요소를 비트 OR 연산
        
        string row = "";
        for (int j = 0; j < n; j++) {
            // 오른쪽에서부터 한 비트씩 확인
            if (map & (1 << (n - 1 - j))) {
                row += '#';  // 비트가 1이면 '#'
            } else {
                row += ' ';  // 비트가 0이면 ' '
            }
        }
        answer.push_back(row);
    }

    return answer;
}

여기서 int map = arr1[i] | arr2[i]; 은
arr1[i] 숫자와 arr2[i] 숫자를 각각 2진수로 변환한 뒤, 각 자리수를 비교하여 둘 중에 하나만 1이어도 1을 반환하여 2진수를 만든 뒤, 이를 10진수로 변환하여 map에 저장하는 코드이다.

for (int j = 0; j < n; j++) {
            // 오른쪽에서부터 한 비트씩 확인
            if (map & (1 << (n - 1 - j))) {
                row += '#';  // 비트가 1이면 '#'
            } else {
                row += ' ';  // 비트가 0이면 ' '
            }
        }

이 부분은, 비트마스크를 사용한 코드이다.
1 << (n-1-j)는 만약 n=5, j=0일 경우 1 << 4이므로 10000 (1을 왼쪽으로 4칸 이동)을 반환하고, map과 &연산자로 비교하는 거다.
위에서 map이 만약 1111이라고 한다면, 1111 & 10000 -> 0000 이므로 비트가 0이되어 공백을 row에 더하게 되고,
j가 1씩 증가하면서 1<<3 (1000), 1<<2 (100), 1<<1 (10), 1<<0 (1) 이 되므로 결국엔 map의 모든 자리수를 하나씩 검사하게 되며 비트가 1이면 #을, 0이면 공백을 row에 더하게 되는 과정이다.

비트 연산의 개념
컴퓨터는 모든 데이터를 이진수(0과 1로 이루어진 값)로 처리한다. 정수형 변수는 메모리 안에 이진수로 저장된다. 예를 들어 9는 2진수로 1001이고, 14는 2진수로 1110이다.

비트 연산은 이러한 이진수 값을 직접 다루는 연산이다. 주요 비트 연산에는 AND(&), OR(|), XOR(^), NOT(~), SHIFT 연산 등이 있다.

비트 OR 연산 (|)
OR 연산(|)은 두 비트 값이 둘 중 하나라도 1이면 1, 둘 다 0이면 0을 반환한다.

예를 들어:

9  => 1001 (2진수)
14 => 1110 (2진수)

9 | 14 => 1111 (2진수) => 15 (10진수)
9 | 14를 계산하면 각 비트를 비교하여 둘 중 하나라도 1이면 결과가 1이 된다.

비트 마스크와 1 << n의 의미
1 << n은 비트 시프트 연산이다. 이는 1을 왼쪽으로 n만큼 밀어라는 의미이다. 즉, 1 << n은 1의 자리에 1을 두고 나머지는 0으로 채우는 숫자를 만드는 방식이다.

예를 들어:

1 << 0 은 0001 (2진수) => 1 (10진수)
1 << 1 은 0010 (2진수) => 2 (10진수)
1 << 2 은 0100 (2진수) => 4 (10진수)
1 << 3 은 1000 (2진수) => 8 (10진수)

비트 AND 연산 (&)
AND 연산(&)은 두 비트 값이 둘 다 1일 때만 1을 반환하고, 그 외에는 0을 반환한다.

예를 들어:

9  => 1001 (2진수)
14 => 1110 (2진수)

9 & 14 => 1000 (2진수) => 8 (10진수)
9 & 14를 계산하면 각 비트를 비교하여 둘 다 1인 자리만 1이 되고, 나머지는 0이 된다.

비트 NOT 연산 (~)
NOT 연산(~)은 비트 순서를 뒤집어서 반환한다.

예를 들어:

~0000 0001 => 0000 1000