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

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

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

들어가며: “부분집합 탐색이 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 이상

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++, 비트연산, 비트마스크, XOR, 알고리즘 등으로 검색하시면 이 글이 도움이 됩니다.