비트 연산은 정수 데이터를 이진수 단위로 다루는 저수준 연산으로, 알고리즘 문제 해결과 시스템 프로그래밍에서 핵심적인 역할을 한다. C++은 여섯 가지 비트 연산자를 제공하여 메모리 효율성과 실행 속도를 극대화할 수 있다.

핵심 연산자 동작 원리

AND 연산 (&)는 두 피연산자의 대응 비트가 모두 1일 때만 1을 반환한다. 플래그 검증이나 특정 비트 마스킹에 활용된다.

int x = 12;   // 1100
int y = 10;   // 1010
int r = x & y; // 1000 (8)

OR 연산 (|)는 어느 한쪽이라도 1이면 1을 반환하여 플래그 설정에 적합하다.

int r = x | y; // 1110 (14)

XOR 연산 (^)는 비트가 서로 다를 때 1을 반환하며, 토글 연산이나 암호화에 쓰인다.

int r = x ^ y; // 0110 (6)

NOT 연산 (~)는 모든 비트를 반전시켜 1의 보수를 생성한다.

unsigned int r = ~x; // ...11110011 (대형 양수)

시프트 연산은 비트 묶음을 좌우로 이동시킨다. 왼쪽 시프트(<<)는 2의 거듭제곱 곱셈, 오른쪽 시프트(>>)는 나눗셈에 상응한다.

int left = x << 2;   // 48, x * 4
int right = x >> 2;  // 3,  x / 4

실전 활용 패턴

최하위 비트 활용으로 홀짝 판별을 즉시 수행한다.

inline bool is_odd(int v) { return v & 1; }

임시 변수 없는 교환은 XOR의 결합법칙을 이용한다.

void exchange(int &p, int &q) {
    p ^= q;
    q ^= p;
    p ^= q;
}

2의 거듭제곱 검증은 비트 패턴 특성을 활용한다. 2의 거듭제곱 수는 단 하나의 1비트만 보유하므로, 자기 자신과 1 감소한 값의 AND가 0이 된다.

bool check_pow2(int v) {
    return v > 0 && !(v & (v - 1));
}

절대값 계산은 부호 비트 추출과 XOR 연산으로 구현한다.

int fast_abs(int v) {
    int sign = v >> 31;           // 부호 확장
    return (v ^ sign) - sign;
}

고급 최적화 기법

비트 제거 반복법으로 1의 개수를 센다. 매 반복마다 최하위 1비트를 제거한다.

int pop_count(int v) {
    int total = 0;
    while (v) {
        v &= v - 1;
        ++total;
    }
    return total;
}

마스크 기반 필드 조작은 특정 비트 영역을 정밀하게 제어한다.

// 하위 4비트 추출
int extract_lower = val & 0x0F;

// n번째 비트 설정 (0-indexed)
val |= (1U << n);

// n번째 비트 해제
val &= ~(1U << n);

// n번째 비트 토글
val ^= (1U << n);

2의 거듭제곱 정렬은 상한값을 구하는 데 사용된다.

int next_pow2(int v) {
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    return v + 1;
}

주의사항

시프트 연산에서 오른쪽 피연산자가 자료형 비트 수 이상이거나 음수인 경우 정의되지 않은 동작이 발생한다. 부호 있는 정수의 오른쪽 시프트는 구현 정의(implementation-defined)이며, 음수에 대한 논리 시프트는 C++에서 제공되지 않는다. 연산자 우선순위 혼란을 방지하기 위해 복합식에 괄호를 명시적으로 사용해야 한다.