비트 연산 기초

비트 연산은 정수의 이진 표현을 직접 조작하는 저수준 연산입니다. 하드웨어에 가까운 연산 특성상 고성능 최적화에 필수적이며, 암호화, 그래픽스, 임베디드 시스템 등에서 광범위하게 활용됩니다.

핵심 연산자

핵 성질

• XOR 성질: a ^ a = 0, a ^ 0 = a, 교환/결합법칙 성립
• 시프트 특성: x << n은 x × 2ⁿ, x >> n은 x / 2 (정수)
• 마스킹: 특정 비트 추출 시 (val >> pos) & 1 또는 val & (1 << pos)

실전 문제 풀이

문제 1: 고유 문자 검증

소문자 문자열 내 모든 문자가 서로 다른지 확인합니다. 26개 소문자를 32비트 정수 하나로 표현하는 비트마스크 기법을 적용합니다.

class UniqueChecker {
public:
    bool hasAllUnique(string str) {
        if (str.length() > 26) return false;
        
        int mask = 0;
        for (char c : str) {
            int pos = c - 'a';
            // 해당 위치 비트가 이미 켜져 있으면 중복
            if (mask & (1 << pos)) return false;
            // 현재 문자 위치 비트 설정
            mask |= (1 << pos);
        }
        return true;
    }
};

문제 2: 누락된 숫자 찾기

[0, n] 범위에서 배열에 빠진 하나의 수를 찾습니다. XOR의 소거 법칙을 활용해 O(n) 시간, O(1) 공간으로 해결합니다.

class MissingFinder {
public:
    int findMissing(vector<int>& arr) {
        int n = arr.size();
        int result = n;  // n은 배열에 없으므로 초기값으로
        
        for (int i = 0; i < n; i++) {
            result ^= arr[i] ^ i;
        }
        return result;
    }
};

문제 3: 덧셈 연산자 없이 합 계산

반가산기 원리를 구현합니다. XOR로 자리올림 없는 합을, AND로 자리올림을 계산하여 반복합니다.

class BitAdder {
public:
    int addWithoutPlus(int x, int y) {
        while (y != 0) {
            int carry = x & y;      // 자리올림 발생 위치
            x = x ^ y;              // 자리올림 없는 합
            y = carry << 1;         // 자리올림을 왼쪽으로 이동
        }
        return x;
    }
};

문제 4: 세 번 등장하는 숫자 중 한 번만 등장하는 수

모든 수가 3번씩 등장하고 하나만 1번 등장할 때, 해당 수를 찾습니다. 각 비트 위치별로 전체 합을 3으로 나눈 나머지로 정답을 재구성합니다.

class SingleNumberFinder {
public:
    int findOnce(vector<int>& data) {
        int answer = 0;
        
        for (int bit = 0; bit < 32; bit++) {
            int bitSum = 0;
            for (int num : data) {
                bitSum += (num >> bit) & 1;
            }
            // 나머지가 1이면 정답의 해당 비트는 1
            if (bitSum % 3 == 1) {
                answer |= (1 << bit);
            }
        }
        return answer;
    }
};

심화 활용

효율적인 비트 조작 패턴

// 최하위 켜진 비트 제거
x &= x - 1;

// 2의 거듭제곱 여부 확인
bool isPowerOfTwo = (x && !(x & (x - 1)));

// 부호 없는 우시프트 (C++20 전용: >>> 대체)
unsigned logicalShift = static_cast<unsigned>(signedVal) >> n;

// 비트 반전 (특정 범위)
int flipRange(int val, int left, int right) {
    int mask = ((1 << (right - left + 1)) - 1) << left;
    return val ^ mask;
}

주의사항

• 시프트 연산자의 우 피연산자가 음수이거나 비트 수 이상이면 미정의 동작
• 부호 있는 정수의 우시프트는 구현 정의(부호 확장 여부)
• 비트마스크 설계 시 오버플로우 방지 (1 << 31은 UB)