C++ 비트 연산 | "비트마스크" 완벽 가이드

들어가며

비트 단위 연산은 플래그 집합을 정수 하나로 표현하거나, 알고리즘에서 상태를 압축할 때 자주 쓰입니다. 이 글에서는 연산자별 의미를 확실히 한 뒤, 이후 절의 예제와 실무 팁을 자신의 코드에 적용할 수 있습니다.

비트 연산은 정수를 비트 단위로 조작하는 연산입니다. 플래그 관리, 메모리 최적화, 알고리즘 최적화에 활용되며, CPU 한 사이클에 실행되어 매우 빠릅니다.

---

1. 비트 연산자

기본 연산자

#include <iostream>
#include <bitset>

int main() {
    // 0b: 이진 리터럴 (C++14)
    int a = 0b1010;  // 10 (이진수 1010)
    int b = 0b1100;  // 12 (이진수 1100)
    
    // std::bitset<4>: 4비트 이진수로 출력
    std::cout << "a: " << std::bitset<4>(a) << " (" << a << ")" << std::endl;
    std::cout << "b: " << std::bitset<4>(b) << " (" << b << ")" << std::endl;
    std::cout << std::endl;
    
    // AND (&): 둘 다 1이면 1, 아니면 0
    // 1010 & 1100 = 1000 (8)
    std::cout << "a & b: " << std::bitset<4>(a & b) << " (" << (a & b) << ")" << std::endl;
    
    // OR (|): 하나라도 1이면 1, 둘 다 0이면 0
    // 1010 | 1100 = 1110 (14)
    std::cout << "a | b: " << std::bitset<4>(a | b) << " (" << (a | b) << ")" << std::endl;
    
    // XOR (^): 다르면 1, 같으면 0
    // 1010 ^ 1100 = 0110 (6)
    std::cout << "a ^ b: " << std::bitset<4>(a ^ b) << " (" << (a ^ b) << ")" << std::endl;
    
    // NOT (~): 비트 반전 (0→1, 1→0)
    // ~1010 = ...11110101 (음수, 2의 보수)
    std::cout << "~a: " << std::bitset<8>(~a) << " (" << (~a) << ")" << std::endl;
    
    // 왼쪽 시프트 (<<): 비트를 왼쪽으로 이동 (×2)
    // 1010 << 1 = 10100 (20)
    std::cout << "a << 1: " << std::bitset<8>(a << 1) << " (" << (a << 1) << ")" << std::endl;
    
    // 오른쪽 시프트 (>>): 비트를 오른쪽으로 이동 (÷2)
    // 1010 >> 1 = 0101 (5)
    std::cout << "a >> 1: " << std::bitset<8>(a >> 1) << " (" << (a >> 1) << ")" << std::endl;
    
    return 0;
}

출력:

a: 1010 (10)
b: 1100 (12)

a & b: 1000 (8)
a | b: 1110 (14)
a ^ b: 0110 (6)
~a: 11110101 (-11)
a << 1: 00010100 (20)
a >> 1: 00000101 (5)

연산자 정리

연산자	이름	설명	예시
&	AND	둘 다 1이면 1	1010 & 1100 = 1000
|	OR	하나라도 1이면 1	1010 | 1100 = 1110
^	XOR	다르면 1	1010 ^ 1100 = 0110
~	NOT	비트 반전	~1010 = ...0101
<<	Left Shift	왼쪽으로 이동 (×2)	1010 << 1 = 10100
>>	Right Shift	오른쪽으로 이동 (÷2)	1010 >> 1 = 0101

---

2. 비트마스크

플래그 관리

#include <iostream>

// 플래그 정의: 각 비트를 하나의 플래그로 사용
// 1 << n: 1을 왼쪽으로 n번 시프트 (n번째 비트만 1)
const int FLAG_READ   = 1 << 0;  // 0b0001 = 1 (0번째 비트)
const int FLAG_WRITE  = 1 << 1;  // 0b0010 = 2 (1번째 비트)
const int FLAG_EXEC   = 1 << 2;  // 0b0100 = 4 (2번째 비트)
const int FLAG_DELETE = 1 << 3;  // 0b1000 = 8 (3번째 비트)
// 각 플래그는 서로 다른 비트를 사용 (겹치지 않음)

int main() {
    int permissions = 0;  // 초기 권한: 없음 (0b0000)
    
    // 플래그 설정 (OR): 특정 비트를 1로 설정
    // |=: OR 후 대입
    permissions |= FLAG_READ;   // 0b0000 | 0b0001 = 0b0001
    permissions |= FLAG_WRITE;  // 0b0001 | 0b0010 = 0b0011
    
    std::cout << "권한: " << permissions << std::endl;  // 3 (0b0011)
    
    // 플래그 체크 (AND): 특정 비트가 1인지 확인
    // &: AND 연산 (해당 비트만 추출)
    if (permissions & FLAG_READ) {  // 0b0011 & 0b0001 = 0b0001 (true)
        std::cout << "읽기 가능" << std::endl;
    }
    
    if (permissions & FLAG_EXEC) {  // 0b0011 & 0b0100 = 0b0000 (false)
        std::cout << "실행 가능" << std::endl;
    } else {
        std::cout << "실행 불가" << std::endl;
    }
    
    // 플래그 해제 (AND NOT): 특정 비트를 0으로 설정
    // ~FLAG_WRITE: 0b0010 → 0b...11111101 (비트 반전)
    // &=: AND 후 대입
    permissions &= ~FLAG_WRITE;  // 0b0011 & 0b...11111101 = 0b0001
    
    std::cout << "쓰기 해제 후: " << permissions << std::endl;  // 1 (0b0001)
    
    // 플래그 토글 (XOR): 특정 비트를 반전 (0→1, 1→0)
    // ^=: XOR 후 대입
    permissions ^= FLAG_EXEC;  // 0b0001 ^ 0b0100 = 0b0101
    
    std::cout << "실행 토글 후: " << permissions << std::endl;  // 5 (0b0101)
    
    return 0;
}

출력:

권한: 3
읽기 가능
실행 불가
쓰기 해제 후: 1
실행 토글 후: 5

---

3. 실전 예제

예제 1: 권한 시스템

#include <iostream>
#include <string>

enum Permission {
    PERM_READ   = 1 << 0,  // 0b0001
    PERM_WRITE  = 1 << 1,  // 0b0010
    PERM_EXEC   = 1 << 2,  // 0b0100
    PERM_DELETE = 1 << 3   // 0b1000
};

class File {
    int permissions = 0;
    std::string name;
    
public:
    File(const std::string& n) : name(n) {}
    
    void grant(int perm) {
        permissions |= perm;
    }
    
    void revoke(int perm) {
        permissions &= ~perm;
    }
    
    bool has(int perm) const {
        return (permissions & perm) == perm;
    }
    
    void printPermissions() const {
        std::cout << "파일: " << name << std::endl;
        std::cout << "  읽기: " << (has(PERM_READ) ? "O" : "X") << std::endl;
        std::cout << "  쓰기: " << (has(PERM_WRITE) ? "O" : "X") << std::endl;
        std::cout << "  실행: " << (has(PERM_EXEC) ? "O" : "X") << std::endl;
        std::cout << "  삭제: " << (has(PERM_DELETE) ? "O" : "X") << std::endl;
    }
};

int main() {
    File file("test.txt");
    
    // 읽기/쓰기 권한 부여
    file.grant(PERM_READ | PERM_WRITE);
    file.printPermissions();
    
    std::cout << std::endl;
    
    // 쓰기 권한 해제
    file.revoke(PERM_WRITE);
    file.printPermissions();
    
    return 0;
}

출력:

파일: test.txt
  읽기: O
  쓰기: O
  실행: X
  삭제: X

파일: test.txt
  읽기: O
  쓰기: X
  실행: X
  삭제: X

예제 2: 비트 트릭

#include <iostream>

// 짝수/홀수 체크
bool isEven(int n) {
    return (n & 1) == 0;
}

// 2의 거듭제곱 체크
bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

// 비트 카운트 (1의 개수)
int countBits(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

// 최하위 비트 추출
int lowestBit(int n) {
    return n & -n;
}

// 최상위 비트 위치
int highestBitPos(int n) {
    int pos = 0;
    while (n >>= 1) ++pos;
    return pos;
}

// 비트 설정
int setBit(int n, int pos) {
    return n | (1 << pos);
}

// 비트 해제
int clearBit(int n, int pos) {
    return n & ~(1 << pos);
}

// 비트 토글
int toggleBit(int n, int pos) {
    return n ^ (1 << pos);
}

// 비트 체크
bool testBit(int n, int pos) {
    return (n & (1 << pos)) != 0;
}

int main() {
    std::cout << "isEven(10): " << isEven(10) << std::endl;  // 1
    std::cout << "isEven(11): " << isEven(11) << std::endl;  // 0
    
    std::cout << "isPowerOfTwo(16): " << isPowerOfTwo(16) << std::endl;  // 1
    std::cout << "isPowerOfTwo(15): " << isPowerOfTwo(15) << std::endl;  // 0
    
    std::cout << "countBits(0b1011): " << countBits(0b1011) << std::endl;  // 3
    
    std::cout << "lowestBit(0b1010): " << lowestBit(0b1010) << std::endl;  // 2
    
    std::cout << "highestBitPos(0b1000): " << highestBitPos(0b1000) << std::endl;  // 3
    
    int n = 0b1010;
    std::cout << "setBit(n, 0): " << std::bitset<4>(setBit(n, 0)) << std::endl;  // 1011
    std::cout << "clearBit(n, 1): " << std::bitset<4>(clearBit(n, 1)) << std::endl;  // 1000
    std::cout << "toggleBit(n, 2): " << std::bitset<4>(toggleBit(n, 2)) << std::endl;  // 1110
    std::cout << "testBit(n, 3): " << testBit(n, 3) << std::endl;  // 1
    
    return 0;
}

---

4. std::bitset

기본 사용

#include <bitset>
#include <iostream>

int main() {
    // 생성
    std::bitset<8> bits1("10101010");
    std::bitset<8> bits2(170);  // 10101010
    
    std::cout << "bits1: " << bits1 << std::endl;
    std::cout << "bits2: " << bits2 << std::endl;
    
    // 비트 설정
    bits1.set(0);     // 10101011
    bits1.reset(1);   // 10101001
    bits1.flip(2);    // 10101101
    
    std::cout << "수정 후: " << bits1 << std::endl;
    
    // 비트 체크
    if (bits1.test(0)) {
        std::cout << "비트 0이 설정됨" << std::endl;
    }
    
    // 카운트
    std::cout << "설정된 비트: " << bits1.count() << std::endl;
    
    // 모두/없음 체크
    std::cout << "모두 설정: " << bits1.all() << std::endl;
    std::cout << "하나라도 설정: " << bits1.any() << std::endl;
    std::cout << "모두 해제: " << bits1.none() << std::endl;
    
    // 변환
    std::cout << "정수: " << bits1.to_ulong() << std::endl;
    std::cout << "문자열: " << bits1.to_string() << std::endl;
    
    return 0;
}

출력:

bits1: 10101010
bits2: 10101010
수정 후: 10101101
비트 0이 설정됨
설정된 비트: 5
모두 설정: 0
하나라도 설정: 1
모두 해제: 0
정수: 173
문자열: 10101101

---

5. 비트 필드

구조체 비트 필드

#include <iostream>

struct Flags {
    unsigned int read : 1;
    unsigned int write : 1;
    unsigned int exec : 1;
    unsigned int reserved : 29;
};

int main() {
    Flags f = {1, 0, 1, 0};
    
    std::cout << "읽기: " << f.read << std::endl;   // 1
    std::cout << "쓰기: " << f.write << std::endl;  // 0
    std::cout << "실행: " << f.exec << std::endl;   // 1
    
    std::cout << "크기: " << sizeof(f) << " bytes" << std::endl;  // 4 bytes
    
    // 수정
    f.write = 1;
    f.exec = 0;
    
    std::cout << "\n수정 후:" << std::endl;
    std::cout << "읽기: " << f.read << std::endl;   // 1
    std::cout << "쓰기: " << f.write << std::endl;  // 1
    std::cout << "실행: " << f.exec << std::endl;   // 0
    
    return 0;
}

---

6. 자주 발생하는 문제

문제 1: 부호 있는 시프트

#include <iostream>

int main() {
    // ❌ 음수 오른쪽 시프트 (구현 정의)
    int x = -8;
    int y = x >> 1;  // -4 (산술 시프트) 또는 다른 값
    
    std::cout << "음수 시프트: " << y << std::endl;
    
    // ✅ 부호 없는 타입
    unsigned int ux = 8;
    unsigned int uy = ux >> 1;  // 4 (논리 시프트, 보장)
    
    std::cout << "부호 없는 시프트: " << uy << std::endl;
    
    return 0;
}

문제 2: 시프트 오버플로우

#include <iostream>

int main() {
    // ❌ 부호 비트로 시프트 (정의되지 않은 동작)
    int x = 1 << 31;  // UB
    
    std::cout << "부호 있는 시프트: " << x << std::endl;
    
    // ✅ 부호 없는 타입
    unsigned int ux = 1u << 31;  // OK
    
    std::cout << "부호 없는 시프트: " << ux << std::endl;
    
    return 0;
}

문제 3: 비트 필드 이식성

#include <iostream>

// ❌ 비트 순서 미정의 (컴파일러 의존)
struct BadFlags {
    unsigned int a : 1;
    unsigned int b : 1;
    unsigned int c : 1;
};

// ✅ 비트마스크 사용 (이식성)
const unsigned int FLAG_A = 1 << 0;
const unsigned int FLAG_B = 1 << 1;
const unsigned int FLAG_C = 1 << 2;

int main() {
    unsigned int flags = 0;
    flags |= FLAG_A;
    flags |= FLAG_C;
    
    std::cout << "플래그: " << flags << std::endl;  // 5 (0b101)
    
    return 0;
}

문제 4: 비트 연산 최적화

#include <iostream>
#include <chrono>

int main() {
    const int N = 100000000;
    
    // 곱셈
    auto start = std::chrono::high_resolution_clock::now();
    volatile int result1 = 0;
    for (int i = 0; i < N; ++i) {
        result1 = i * 8;
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto mul_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    // 시프트
    start = std::chrono::high_resolution_clock::now();
    volatile int result2 = 0;
    for (int i = 0; i < N; ++i) {
        result2 = i << 3;
    }
    end = std::chrono::high_resolution_clock::now();
    auto shift_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    std::cout << "곱셈: " << mul_time.count() << "ms" << std::endl;
    std::cout << "시프트: " << shift_time.count() << "ms" << std::endl;
    
    // 현대 컴파일러는 자동 최적화하므로 차이 거의 없음
    
    return 0;
}

---

7. 실전 예제: 비트마스크 DP

#include <iostream>
#include <vector>
#include <algorithm>

// 외판원 순회 문제 (TSP) - 비트마스크 DP
class TSP {
    int n;
    std::vector<std::vector<int>> dist;
    std::vector<std::vector<int>> dp;
    
public:
    TSP(const std::vector<std::vector<int>>& distances) 
        : n(distances.size()), dist(distances) {
        dp.assign(1 << n, std::vector<int>(n, -1));
    }
    
    int solve(int visited, int current) {
        // 모두 방문
        if (visited == (1 << n) - 1) {
            return dist[current][0];  // 시작점으로
        }
        
        // 메모이제이션
        if (dp[visited][current] != -1) {
            return dp[visited][current];
        }
        
        int minCost = 1e9;
        
        // 다음 도시 선택
        for (int next = 0; next < n; ++next) {
            // 아직 방문 안한 도시
            if (!(visited & (1 << next))) {
                int cost = dist[current][next] + 
                          solve(visited | (1 << next), next);
                minCost = std::min(minCost, cost);
            }
        }
        
        return dp[visited][current] = minCost;
    }
    
    int findMinPath() {
        return solve(1, 0);  // 0번 도시에서 시작
    }
};

int main() {
    std::vector<std::vector<int>> dist = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    
    TSP tsp(dist);
    std::cout << "최소 경로 비용: " << tsp.findMinPath() << std::endl;
    
    return 0;
}

---

정리

핵심 요약

1. 비트 연산자: &, |, ^, ~, <<, >>
2. 비트마스크: 플래그 관리 (설정, 해제, 체크, 토글)
3. 비트 필드: 메모리 최적화 (이식성 낮음)
4. bitset: 편리한 비트 조작
5. 비트 트릭: 짝수 체크, 2의 거듭제곱, 비트 카운트
6. 성능: CPU 한 사이클 (매우 빠름)

비트 연산 활용

활용	기법	예시
플래그 설정	|=	flags |= FLAG_READ
플래그 해제	&= ~	flags &= ~FLAG_WRITE
플래그 체크	&	if (flags & FLAG_EXEC)
플래그 토글	^=	flags ^= FLAG_DELETE
짝수 체크	& 1	if ((n & 1) == 0)
2의 거듭제곱	& (n-1)	if (n & (n-1) == 0)

실전 팁

사용 원칙:

• 플래그 관리는 비트마스크
• 메모리 최적화는 비트 필드
• 편리한 조작은 bitset
• 알고리즘은 비트 트릭

성능:

• 비트 연산은 매우 빠름 (1 사이클)
• 컴파일러가 자동 최적화
• bitset은 약간 느림 (편의성 트레이드오프)
• 비트마스크 DP는 O(2ⁿ·n) 최적화

주의사항:

• 부호 있는 시프트는 구현 정의
• 시프트 오버플로우 주의
• 비트 필드는 이식성 낮음
• 가독성 고려 (주석 추가)

다음 단계

• C++ Bitset
• C++ Bit Operations
• Algorithm Bitmask DP

---

관련 글

• C++ 비트 연산 완벽 가이드 | 비트마스크 DP·XOR·해밍 거리·비트셋 [실전]