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

· 35분 읽기 · 수정 고급 실습
C++ 비트 연산 완벽 가이드 | 비트마스크 DP·XOR·해밍 거리·비트셋 [실전]

이 글의 핵심

C++ 비트 연산 활용: 비트마스크 DP, XOR 트릭, 비트 카운팅, 해밍 거리, std::bitset. 문제 시나리오, 완전한 예제, 흔한 실수, 성능 팁, 프로덕션 패턴. 부분집합을 나열하거나, 상태를 압축해 DP로 풀어야 할 때 배열·벡터로 상태를 관리하면 메모리와 시간이 폭발합니다. 비유하면 "30개 원소의 부분집합을 벡터로 저장하는 것"과 "30비트 정수 하나로 표현하는 것"의 차이입니다.

들어가며: “부분집합 탐색이 2초 제한에 걸려요”

비트 연산 선택의 함정

부분집합을 나열하거나, 상태를 압축해 DP로 풀어야 할 때 배열·벡터로 상태를 관리하면 메모리와 시간이 폭발합니다. 비유하면 “30개 원소의 부분집합을 벡터로 저장하는 것”과 “30비트 정수 하나로 표현하는 것”의 차이입니다.

flowchart TD
  subgraph wrong[❌ 벡터/집합으로 상태 관리]
    W1[vector<int> visited] --> W2[메모리 O(n)]
    W2 --> W3[해시/비교 비용]
    W3 --> W4[시간 초과]
  end
  subgraph right[✅ 비트마스크로 상태 압축]
    R1[uint32_t mask] --> R2[메모리 O(1)]
    R2 --> R3[비트 연산 O(1)]
    R3 --> R4[수십 배 빠름]
  end

이 글에서는 실제로 겪는 문제 시나리오부터 시작해, 비트마스크 DP, XOR 트릭, 비트 카운팅, 해밍 거리, std::bitset의 완전한 구현, 자주 하는 실수, 성능 최적화 팁, 프로덕션 패턴까지 단계별로 다룹니다.

이 글을 읽으면:

  • 비트 연산의 핵심 개념을 이해할 수 있습니다.
  • 비트마스크 DP로 부분집합·순열 문제를 풀 수 있습니다.
  • XOR, 해밍 거리, 비트셋을 실전에 활용할 수 있습니다.

요구 환경: C++17 이상

실무 적용 경험: 이 글은 대규모 C++ 프로젝트에서 실제로 겪은 문제와 해결 과정을 바탕으로 작성되었습니다. 책이나 문서에서 다루지 않는 실전 함정과 디버깅 팁을 포함합니다.

목차

  1. 문제 시나리오
  2. 기본 개념
  3. 완전한 비트 연산 예제
  4. 자주 발생하는 에러와 해결법
  5. 성능 최적화 팁
  6. 프로덕션 패턴
  7. 구현 체크리스트

1. 문제 시나리오

시나리오 1: 부분집합 탐색 시간 초과

상황: n개 원소의 모든 부분집합을 탐색해야 하는데, n=20에서 2초 제한에 걸립니다.

잘못된 접근: vector<int>로 부분집합을 만들고 set<vector<int>>에 저장하면, 비교·해시 비용이 커서 느립니다.

해결: 비트마스크로 0~2^n-1 정수가 곧 부분집합입니다. i번 비트가 1이면 i번 원소 포함. O(2^n) 반복만으로 처리 가능합니다.

시나리오 2: 짝이 맞지 않는 원소 찾기

상황: 배열에서 “한 개만 홀수 번 등장하는 원소”를 O(n) 시간, O(1) 공간으로 찾아야 합니다.

잘못된 접근: 해시맵으로 카운트하면 O(n) 공간이 필요합니다.

해결: XOR의 성질 a ^ a = 0, a ^ 0 = a를 이용해, 모든 원소를 XOR하면 홀수 번 등장한 원소만 남습니다.

시나리오 3: 두 수의 이진 표현 차이

상황: 에러 정정 코드, DNA 서열 비교에서 두 값의 비트가 몇 개 다른지 세어야 합니다.

잘못된 접근: 문자열로 변환해 한 비트씩 비교하면 느리고 코드가 길어집니다.

해결: 해밍 거리 = __builtin_popcount(a ^ b). XOR로 다른 비트만 1로 만들고, 1의 개수를 셉니다.

시나리오 4: TSP(외판원 문제) 상태 압축

상황: n개 도시를 한 번씩 방문하는 최단 경로. n=20이면 20!은 불가능하지만, “지금까지 방문한 도시 집합”을 상태로 두면 DP로 풀 수 있습니다.

잘못된 접근: set<int>로 방문 집합을 표현하면 해시 비용이 큽니다.

해결: 비트마스크 DP dp[mask][cur] = “mask에 해당하는 도시들을 방문하고 cur에 있을 때 최소 비용”. mask는 20비트 정수로 표현합니다.

시나리오 5: 플래그·권한 관리

상황: 읽기/쓰기/실행 등 여러 권한을 효율적으로 저장하고 검사해야 합니다.

잘못된 접근: bool read, write, execute 등 개별 변수로 관리하면 확장성이 떨어집니다.

해결: 비트 플래그 READ=1, WRITE=2, EXEC=4로 정의하고, flags & READ로 검사, flags |= WRITE로 추가합니다.

알고리즘 선택 가이드

문제 유형추천 기법시간 복잡도
부분집합 열거비트마스크O(2^n)
홀수 번 등장 원소XORO(n)
비트 차이 개수해밍 거리 (popcount)O(1)
TSP, 상태 DP비트마스크 DPO(2^n × n²)
플래그/권한비트 플래그O(1)
큰 비트 집합std::bitsetO(n/64)

2. 기본 개념

비트 연산자 요약

flowchart LR
  subgraph ops[비트 연산자]
    A[AND &] --> A1[둘 다 1이면 1]
    B[OR \|] --> B1[하나라도 1이면 1]
    C[XOR ^] --> C1[다르면 1]
    D[NOT ~] --> D1[비트 반전]
    E[시프트 << >>] --> E1[왼쪽/오른쪽 이동]
  end
연산자의미예시
&AND5 & 3 = 1
|OR5 | 3 = 7
^XOR5 ^ 3 = 6
~NOT~0 = -1 (부호 있는)
<<왼쪽 시프트1 << 3 = 8
>>오른쪽 시프트8 >> 2 = 2

핵심 XOR 성질

// XOR의 핵심 성질 (암기 권장)
// 1. a ^ a = 0  (자기 자신과 XOR하면 소멸)
// 2. a ^ 0 = a  (0과 XOR하면 그대로)
// 3. a ^ b = b ^ a  (교환법칙)
// 4. (a ^ b) ^ c = a ^ (b ^ c)  (결합법칙)

int a = 5, b = 5;
int c = a ^ b;  // c = 0 (같은 수 XOR)

int arr[] = {3, 3, 7, 7, 9};  // 9만 홀수 번
int single = 0;
for (int x : arr) single ^= x;  // single = 9

비트마스크 기본 패턴

// n개 원소, i번째(0-based) 비트 조작
const int n = 8;

// i번 비트 포함 (1로 설정)
int mask = 0;
mask |= (1 << i);           // i번 비트 켜기

// i번 비트 제거 (0으로 설정)
mask &= ~(1 << i);          // i번 비트 끄기

// i번 비트 토글
mask ^= (1 << i);

// i번 비트 검사
bool has = (mask & (1 << i)) != 0;
// 또는: bool has = (mask >> i) & 1;

// 부분집합 크기 (1의 개수)
int cnt = __builtin_popcount(mask);  // GCC/Clang
// C++20: #include <bit>
// int cnt = std::popcount(static_cast<unsigned>(mask));

// 최하위 1 비트만 추출
int lowbit = mask & (-mask);  // 또는 mask & (~mask + 1)

// 모든 부분집합 순회 (공집합 제외)
for (int sub = mask; sub; sub = (sub - 1) & mask) {
    // sub는 mask의 부분집합
}

비트 시프트 주의점

// 왼쪽 시프트: 부호 없는 타입 사용 권장
unsigned int a = 1u << 31;   // OK: 2^31
int b = 1 << 31;             // UB: 부호 있는 정수 오버플로우

// 오른쪽 시프트: 부호 있는 타입은 구현 정의(산술 시프트)
int x = -8;
x >> 1;  // -4 (산술 시프트) 또는 큰 양수 (논리 시프트)
// 권장: unsigned 사용
unsigned u = 0xFFFFFFF8u;  // -8의 비트 패턴
u >> 1;  // 0x7FFFFFFC (논리 시프트, 정의됨)

3. 완전한 비트 연산 예제

3.1 비트마스크로 부분집합 열거

문제: n개 원소의 모든 부분집합을 생성합니다.

#include <vector>
#include <iostream>

void enumerateSubsets(const std::vector<int>& arr) {
    const int n = static_cast<int>(arr.size());
    // 0 ~ 2^n - 1: 각 정수가 하나의 부분집합에 대응
    for (int mask = 0; mask < (1 << n); ++mask) {
        std::vector<int> subset;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                subset.push_back(arr[i]);
            }
        }
        // subset 처리 (출력, 합 계산 등)
        for (int x : subset) std::cout << x << " ";
        std::cout << "\n";
    }
}

// 사용 예시
void example_subset() {
    std::vector<int> arr = {1, 2, 3};
    enumerateSubsets(arr);
    // 출력: (공집합), 1, 2, 1 2, 3, 1 3, 2 3, 1 2 3
}

3.2 XOR로 홀수 번 등장 원소 찾기

문제: 배열에서 정확히 한 번만 등장하는 원소를 O(n) 시간, O(1) 공간으로 찾습니다.

#include <vector>

// 한 개만 홀수 번 등장
int findSingle(const std::vector<int>& arr) {
    int result = 0;
    for (int x : arr) {
        result ^= x;
    }
    return result;
}

// 두 개가 홀수 번 등장하는 경우: 둘을 분리
std::pair<int, int> findTwoSingles(const std::vector<int>& arr) {
    int xor_all = 0;
    for (int x : arr) xor_all ^= x;
    // xor_all = a ^ b (a, b가 찾을 두 수)
    // 최하위 1 비트: a와 b가 다른 위치
    int diff_bit = xor_all & (-xor_all);
    int a = 0, b = 0;
    for (int x : arr) {
        if (x & diff_bit)
            a ^= x;
        else
            b ^= x;
    }
    return {a, b};
}

// 사용 예시
void example_xor() {
    std::vector<int> v1 = {4, 2, 4, 2, 7};  // 7만 한 번
    int s = findSingle(v1);  // s = 7

    std::vector<int> v2 = {1, 2, 1, 2, 3, 4};  // 3, 4가 한 번씩
    auto [a, b] = findTwoSingles(v2);  // a=3, b=4 또는 a=4, b=3
}

3.3 해밍 거리 (Hamming Distance)

문제: 두 정수의 이진 표현에서 다른 비트의 개수를 구합니다.

#include <bit>  // C++20
#include <cstdint>

// 방법 1: __builtin_popcount (GCC/Clang)
int hammingDistanceBuiltin(int a, int b) {
    return __builtin_popcount(static_cast<unsigned>(a ^ b));
}

// 방법 2: C++20 std::popcount
#if __cplusplus >= 202002L
int hammingDistanceCpp20(unsigned a, unsigned b) {
    return std::popcount(a ^ b);
}
#endif

// 방법 3: 수동 구현 (이식성)
int popcountManual(uint32_t x) {
    int count = 0;
    while (x) {
        count += x & 1;
        x >>= 1;
    }
    return count;
}

// Brian Kernighan 방식: 1의 개수만큼만 반복
int popcountKernighan(uint32_t x) {
    int count = 0;
    while (x) {
        x &= (x - 1);  // 최하위 1 제거
        ++count;
    }
    return count;
}

int hammingDistance(int a, int b) {
    return popcountKernighan(static_cast<uint32_t>(a ^ b));
}

3.4 비트마스크 DP: TSP (외판원 문제)

문제: n개 도시를 한 번씩 방문하고 출발지로 돌아오는 최단 경로. dp[mask][cur] = mask 도시들을 방문하고 cur에 있을 때 최소 비용.

flowchart TD
  subgraph states[상태 전이]
    S0["dp[0001][0] = 0\n0번만 방문"]
    S1["dp[0011][1] = dist[0][1]"]
    S2["dp[0111][2] = ..."]
    S3["dp[1111][3] + dist[3][0]"]
  end
  S0 --> S1 --> S2 --> S3
#include <vector>
#include <algorithm>
#include <climits>

const int INF = INT_MAX / 2;

int tsp(const std::vector<std::vector<int>>& dist) {
    const int n = static_cast<int>(dist.size());
    const int full = (1 << n) - 1;
    // dp[mask][cur]: mask 도시 방문 후 cur에 있을 때 최소 비용
    std::vector<std::vector<int>> dp(1 << n, std::vector<int>(n, INF));
    dp[1][0] = 0;  // 0번 도시에서 시작

    for (int mask = 1; mask <= full; ++mask) {
        for (int cur = 0; cur < n; ++cur) {
            if (dp[mask][cur] == INF) continue;
            if ((mask & (1 << cur)) == 0) continue;

            for (int next = 0; next < n; ++next) {
                if (mask & (1 << next)) continue;  // 이미 방문
                int new_mask = mask | (1 << next);
                int new_cost = dp[mask][cur] + dist[cur][next];
                dp[new_mask][next] = std::min(dp[new_mask][next], new_cost);
            }
        }
    }

    // 전체 방문 후 0번으로 돌아가는 비용
    int ans = INF;
    for (int cur = 1; cur < n; ++cur) {
        if (dp[full][cur] != INF && dist[cur][0] != INF) {
            ans = std::min(ans, dp[full][cur] + dist[cur][0]);
        }
    }
    return ans;
}

// 사용 예시
void example_tsp() {
    std::vector<std::vector<int>> dist = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    int result = tsp(dist);  // 최단 경로 비용
}

3.5 std::bitset 활용

문제: 64비트를 넘는 큰 비트 집합을 다룰 때, std::bitset이 메모리·연산 모두 효율적입니다.

#include <bitset>
#include <iostream>
#include <string>
#include <vector>

void example_bitset() {
    // 8비트 비트셋
    std::bitset<8> b1(0b10101010);
    std::bitset<8> b2("11110000");

    // 연산
    auto and_result = b1 & b2;
    auto or_result  = b1 | b2;
    auto xor_result = b1 ^ b2;
    auto not_result = ~b1;

    // 접근
    b1[0] = 1;           // 0번 비트 설정
    bool bit = b1.test(3);  // 3번 비트 검사
    b1.set(2);            // 2번 비트를 1로
    b1.reset(2);         // 2번 비트를 0으로
    b1.flip(2);          // 2번 비트 토글

    // 정보
    size_t ones = b1.count();   // 1의 개수
    size_t size = b1.size();    // 비트 수
    bool any = b1.any();        // 1이 하나라도 있는가
    bool all = b1.all();        // 모두 1인가
    bool none = b1.none();      // 모두 0인가

    // 문자열 변환
    std::string s = b1.to_string();
    unsigned long ul = b1.to_ulong();
}

// 에라토스테네스 체 (비트셋으로 소수 표시)
std::vector<int> sievePrimes(int n) {
    std::bitset<1000001> is_prime;
    is_prime.set();
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
    std::vector<int> primes;
    for (int i = 2; i <= n; ++i)
        if (is_prime[i]) primes.push_back(i);
    return primes;
}

3.6 실전 문제: 부분집합 합 (Subset Sum)

문제: n개 원소 중 합이 target인 부분집합이 있는지 판별합니다. 비트마스크로 모든 부분집합의 합을 O(2^n)에 계산합니다.

#include <vector>
#include <unordered_set>

bool hasSubsetSum(const std::vector<int>& arr, int target) {
    const int n = static_cast<int>(arr.size());
    for (int mask = 0; mask < (1 << n); ++mask) {
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) sum += arr[i];
        }
        if (sum == target) return true;
    }
    return false;
}

// 최적화: 중간에서 만나기 (Meet in the Middle)
// n이 40일 때 2^40은 불가능하지만, 절반씩 나누면 2^20 × 2 가능
bool hasSubsetSumMeetInMiddle(const std::vector<int>& arr, int target) {
    const int n = static_cast<int>(arr.size());
    const int half = n / 2;
    std::unordered_set<int> left_sums;
    for (int mask = 0; mask < (1 << half); ++mask) {
        int sum = 0;
        for (int i = 0; i < half; ++i)
            if (mask & (1 << i)) sum += arr[i];
        left_sums.insert(sum);
    }
    for (int mask = 0; mask < (1 << (n - half)); ++mask) {
        int sum = 0;
        for (int i = 0; i < n - half; ++i)
            if (mask & (1 << i)) sum += arr[half + i];
        if (left_sums.count(target - sum)) return true;
    }
    return false;
}

3.7 비트 플래그 (권한 관리)

#include <cstdint>

enum class Permission : uint8_t {
    None   = 0,
    Read   = 1 << 0,   // 0b001
    Write  = 1 << 1,   // 0b010
    Execute = 1 << 2,  // 0b100
};

// 조합
constexpr uint8_t ReadWrite = static_cast<uint8_t>(Permission::Read) |
                              static_cast<uint8_t>(Permission::Write);

bool hasPermission(uint8_t flags, Permission p) {
    return (flags & static_cast<uint8_t>(p)) != 0;
}

void addPermission(uint8_t& flags, Permission p) {
    flags |= static_cast<uint8_t>(p);
}

void removePermission(uint8_t& flags, Permission p) {
    flags &= ~static_cast<uint8_t>(p);
}

void example_flags() {
    uint8_t user = static_cast<uint8_t>(Permission::Read);
    addPermission(user, Permission::Write);
    bool canWrite = hasPermission(user, Permission::Write);  // true
    removePermission(user, Permission::Read);
}

4. 자주 발생하는 에러와 해결법

에러 1: 부호 있는 정수 시프트 오버플로우

증상: 1 << 31이 음수가 되거나, undefined behavior로 인한 예측 불가 동작.

원인: C++에서 부호 있는 정수의 오버플로우는 undefined behavior입니다.

// ❌ 잘못된 코드
int mask = 1 << 31;  // UB
for (int i = 0; i < 32; ++i) {
    int bit = 1 << i;  // i=31에서 UB
}

// ✅ 올바른 코드
unsigned int mask = 1u << 31;
for (int i = 0; i < 32; ++i) {
    unsigned int bit = 1u << i;
}

에러 2: 연산자 우선순위

증상: mask & 1 == 0이 의도와 다르게 동작합니다.

원인: ==가 &보다 우선순위가 높아 mask & (1 == 0)으로 해석됩니다.

// ❌ 잘못된 코드
if (mask & 1 == 0) {  // 항상 mask & 0 = 0 → false
    // ...
}

// ✅ 올바른 코드
if ((mask & 1) == 0) {
    // ...
}

에러 3: 1의 개수 셀 때 부호 확장

증상: __builtin_popcount(-1)이 32 또는 64가 아닌 이상한 값.

원인: __builtin_popcount는 unsigned를 기대합니다. 음수는 부호 확장으로 많은 비트가 1이 됩니다.

// ❌ 잘못된 코드
int x = -1;
int cnt = __builtin_popcount(x);  // 부호 있는 정수

// ✅ 올바른 코드
int x = -1;
int cnt = __builtin_popcount(static_cast<unsigned>(x));
// 또는
int cnt = __builtin_popcount(static_cast<uint32_t>(x));

에러 4: 비트마스크 범위 초과

증상: n=32일 때 1 << 32가 0이 됩니다.

원인: 시프트 연산에서 1 << 32는 undefined behavior (32비트 정수에서). 시프트량은 0~(비트수-1)이어야 합니다.

// ❌ 잘못된 코드
int n = 32;
for (int mask = 0; mask < (1 << n); ++mask)  // 1 << 32는 UB

// ✅ 올바른 코드: n < 32일 때
unsigned full = (n < 32) ? (1u << n) : ~0u;
for (unsigned mask = 0; mask < full; ++mask) { /* ... */ }

// n이 32 이상이면 64비트 사용
#include <cstdint>
int n = 35;
uint64_t full = (n < 64) ? (1ULL << n) : 0ULL;

에러 5: 오른쪽 시프트의 구현 정의 동작

증상: -1 >> 1이 플랫폼마다 다릅니다.

원인: 부호 있는 정수의 오른쪽 시프트는 “산술 시프트”인지 “논리 시프트”인지 구현 정의입니다.

// ❌ 잘못된 코드
int x = -8;
int y = x >> 1;  // -4 또는 큰 양수 (플랫폼 의존)

// ✅ 올바른 코드: unsigned 사용
unsigned x = 0xFFFFFFF8u;
unsigned y = x >> 1;  // 0x7FFFFFFC (항상 동일)

에러 6: 비트마스크 DP에서 초기화 누락

증상: TSP 등에서 답이 INF로 나오거나 잘못된 값.

원인: dp[1][0] = 0처럼 시작 상태를 초기화하지 않거나, INF 값이 너무 작아 오버플로우.

// ❌ 잘못된 코드
std::vector<std::vector<int>> dp(1 << n, std::vector<int>(n, INF));
// dp[1][0] 초기화 안 함

// ✅ 올바른 코드
dp[1][0] = 0;  // 0번 도시에서 시작, 0번만 방문한 상태
// INF는 INT_MAX/2 등 오버플로우 방지

5. 성능 최적화 팁

팁 1: unsigned 사용

부호 있는 정수는 시프트·비트 연산에서 UB와 구현 정의 동작이 많습니다. 비트 연산에는 unsigned 또는 uint32_t/uint64_t를 사용하세요.

// ✅ 권장
uint32_t mask = 0;
uint64_t big_mask = 0;

팁 2: __builtin 함수 활용 (GCC/Clang)

// 1의 개수
__builtin_popcount(x);      // 32비트
__builtin_popcountll(x);    // 64비트

// 최하위 1의 위치 (0-based)
__builtin_ffs(x) - 1;       // x=0이면 0 반환 (주의)

// 앞쪽 0의 개수
__builtin_clz(x);           // x=0이면 UB
__builtin_clzll(x);

// 뒤쪽 0의 개수
__builtin_ctz(x);           // x=0이면 UB
__builtin_ctzll(x);

// C++20에서는 <bit> 헤더의 std::popcount, std::countl_zero 등 사용

팁 3: 부분집합 순회 최적화

mask의 모든 부분집합을 순회할 때, (sub - 1) & mask로 다음 부분집합을 O(1)에 구합니다.

// mask의 모든 부분집합 (공집합 제외)
for (int sub = mask; sub; sub = (sub - 1) & mask) {
    // sub는 mask의 진부분집합
}
// 반복 횟수: 2^(popcount(mask)) - 1

팁 4: 비트마스크 DP 메모리 절약

상태가 dp[mask][cur] 형태일 때, cur가 mask에 포함되어야 하므로 cur를 루프에서 mask에 포함된 것만 순회하면 됩니다. 또한 mask를 작은 것부터 채우면 이전 레이어만 필요해 공간을 절반으로 줄일 수 있는 경우가 있습니다.

// 2차원 대신 1차원으로 롤링 (상황에 따라)
std::vector<int> dp_cur(1 << n, INF), dp_next(1 << n, INF);
dp_cur[1] = 0;
for (int len = 1; len < n; ++len) {
    dp_next.assign(1 << n, INF);
    for (int mask = 0; mask < (1 << n); ++mask) {
        // ...
    }
    std::swap(dp_cur, dp_next);
}

팁 5: std::bitset vs 수동 비트마스크

  • n ≤ 64: uint64_t 비트마스크가 가장 빠름.
  • n > 64: std::bitset<N>이 메모리 효율적이고, count(), &, | 등이 최적화되어 있음.
  • 동적 크기: std::vector<bool> 또는 std::bitset을 여러 개 사용.

팁 6: 컴파일 타임 상수

비트 크기가 컴파일 타임에 알려지면, constexpr와 std::bitset<N>으로 최적화가 잘 됩니다.

constexpr int N = 20;
std::bitset<N> mask;
std::array<int, 1 << N> dp;  // N이 작을 때만

6. 프로덕션 패턴

패턴 1: 타입 안전 비트 플래그

#include <type_traits>

template<typename E>
struct BitFlags {
    using U = std::underlying_type_t<E>;
    U value = 0;

    constexpr BitFlags() = default;
    constexpr explicit BitFlags(U v) : value(v) {}
    constexpr BitFlags(E e) : value(static_cast<U>(e)) {}

    constexpr bool test(E e) const {
        return (value & static_cast<U>(e)) != 0;
    }
    constexpr void set(E e) { value |= static_cast<U>(e); }
    constexpr void reset(E e) { value &= ~static_cast<U>(e); }
    constexpr void flip(E e) { value ^= static_cast<U>(e); }

    constexpr BitFlags operator|(E e) const {
        return BitFlags(value | static_cast<U>(e));
    }
};

enum class Flag : uint8_t { A = 1, B = 2, C = 4 };
using Flags = BitFlags<Flag>;

void use_flags() {
    Flags f(Flag::A);
    f.set(Flag::B);
    if (f.test(Flag::B)) { /* ... */ }
}

패턴 2: 비트 조작 유틸리티 클래스

#include <cstdint>
#include <bit>

struct BitUtils {
    static constexpr int popcount(uint32_t x) {
#if __cplusplus >= 202002L
        return std::popcount(x);
#else
        return __builtin_popcount(x);
#endif
    }
    static constexpr int popcount(uint64_t x) {
#if __cplusplus >= 202002L
        return std::popcount(x);
#else
        return __builtin_popcountll(x);
#endif
    }
    static constexpr uint32_t lowbit(uint32_t x) {
        return x & (-x);
    }
    static constexpr bool isPowerOfTwo(uint32_t x) {
        return x && !(x & (x - 1));
    }
};

패턴 3: 네트워크/프로토콜에서 바이트 순서

#include <cstdint>
#include <algorithm>

// 빅 엔디안 ↔ 호스트 순서 변환
uint32_t ntohl(uint32_t net) {
    uint8_t* p = reinterpret_cast<uint8_t*>(&net);
    return (static_cast<uint32_t>(p[0]) << 24) |
           (static_cast<uint32_t>(p[1]) << 16) |
           (static_cast<uint32_t>(p[2]) << 8) |
           static_cast<uint32_t>(p[3]);
}

// 또는 C++20 std::endian
#include <bit>
uint32_t swapEndian(uint32_t x) {
    if constexpr (std::endian::native == std::endian::little) {
        return __builtin_bswap32(x);
    }
    return x;
}

패턴 4: 압축/인코딩에서 비트 패킹

#include <cstdint>
#include <vector>

// 여러 작은 값을 하나의 정수에 패킹
// 예: 0~15 값 4개를 uint64_t 하나에
uint64_t pack(uint8_t a, uint8_t b, uint8_t c, uint8_t d) {
    return (uint64_t)a | ((uint64_t)b << 16) |
           ((uint64_t)c << 32) | ((uint64_t)d << 48);
}
void unpack(uint64_t packed, uint8_t& a, uint8_t& b, uint8_t& c, uint8_t& d) {
    a = packed & 0xFFFF;
    b = (packed >> 16) & 0xFFFF;
    c = (packed >> 32) & 0xFFFF;
    d = (packed >> 48) & 0xFFFF;
}

7. 구현 체크리스트

비트 연산 일반

  • 비트 연산에 unsigned 또는 uint32_t/uint64_t 사용
  • 1 << n에서 n이 비트 수 미만인지 확인
  • &, | 등과 == 사용 시 괄호로 우선순위 명시
  • __builtin_popcount에 부호 있는 정수 넘기지 않기

비트마스크 DP

  • 시작 상태 dp[초기mask][시작점] = 0 초기화
  • INF 값이 오버플로우되지 않도록 INT_MAX/2 등 사용
  • mask에 cur가 포함된 경우만 유효한 상태인지 확인

XOR 활용

  • “홀수 번 등장” 문제에 XOR 적용 가능한지 검토
  • 두 개 찾기 시 분리 비트 선택 로직 검증

프로덕션

  • 플래그/권한은 enum + 비트 연산으로 타입 안전하게
  • 플랫폼 이식성 필요 시 std::bit(C++20) 또는 조건부 __builtin_ 사용
  • 바이트 순서(엔디안) 변환 시 명시적 처리

정리

항목설명
비트마스크부분집합·상태를 정수로 압축, DP·열거에 활용
XOR홀수 번 등장 원소, 해밍 거리 계산
해밍 거리popcount(a ^ b)
비트셋64비트 초과 시 std::bitset
주의점unsigned 사용, 시프트 UB, 연산자 우선순위

핵심 원칙:

  1. 비트 연산에는 unsigned 타입 사용
  2. XOR 성질 a^a=0, a^0=a 활용
  3. 비트마스크로 상태 압축 시 메모리·속도 이득
  4. 프로덕션에서는 타입 안전 래퍼 고려

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. 압축 알고리즘, 암호화, 네트워크 프로토콜(플래그, 바이트 순서), 최적화 문제(비트마스크 DP), 플래그·권한 관리, 에러 정정 코드 등에 활용합니다.

Q. 선행으로 읽으면 좋은 글은?

A. C++ 기본 연산자, 동적 계획법 기초, STL 컨테이너를 먼저 익히면 좋습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference bit manipulation, LeetCode 비트 연산 유형, 《Hacker’s Delight》 서적을 참고하세요.

한 줄 요약: 비트마스크·XOR·해밍 거리를 마스터하면 상태 압축과 최적화 문제를 효율적으로 풀 수 있습니다.

참고 자료

관련 글

  • C++ 탐욕 알고리즘 완벽 가이드 | 활동 선택·분수 배낭·허프만 코딩·구간 스케줄링 [실전]
  • C++ bitset |
  • C++ 알고리즘 |
... 996 lines not shown ... Token usage: 63706/1000000; 936294 remaining Start-Sleep -Seconds 3