C++ 비트 조작 최적화 기법

개요

비트 조작은 플래그 관리, 마스킹, 집합 연산, 해시, 압축 데이터 등 다양한 분야에서 조건문이나 나눗셈보다 훨씬 빠른 연산을 제공합니다. C++20의 <bit> 헤더는 이식 가능한 표준 비트 유틸리티를 제공합니다.

연산	일반 코드	비트 코드	차이
짝수 판별	n % 2 == 0	!(n & 1)	나눗셈 vs AND
2배 곱하기	n * 2	n << 1	곱셈 vs 시프트
절댓값 부호 확인	n < 0	n >> 31 & 1	분기 vs 시프트
최솟값	min(a,b)	b ^ ((a^b) & -(a<b))	분기 제거

---

1. 기본 비트 연산

uint32_t flags = 0;

// 비트 설정
flags |= (1u << 3);       // 3번 비트 ON

// 비트 해제
flags &= ~(1u << 3);      // 3번 비트 OFF

// 비트 토글
flags ^= (1u << 3);       // 3번 비트 반전

// 비트 확인
bool is_set = (flags >> 3) & 1u;

// 최하위 비트(LSB) 추출
uint32_t lsb = flags & (-flags);

// 최하위 비트 제거
flags &= flags - 1;

// 2의 거듭제곱 확인
bool is_power_of_2 = n && !(n & (n - 1));

---

2. C++20 <bit> 헤더

#include <bit>
#include <cstdint>

uint32_t v = 0b1010'0110;

// 1인 비트 개수 (popcount)
int ones = std::popcount(v);         // 4

// 선행 0 개수
int lz = std::countl_zero(v);        // 24 (32비트 기준)

// 후행 0 개수 (최하위 SET 비트 위치)
int tz = std::countr_zero(v);        // 1

// 선행 1 개수
int lo = std::countl_one(~v);

// 비트 순환 이동
uint32_t rotated = std::rotl(v, 3);  // 왼쪽 3칸
uint32_t rotr    = std::rotr(v, 1);  // 오른쪽 1칸

// 2의 거듭제곱으로 올림
uint32_t next2 = std::bit_ceil(v);   // v보다 크거나 같은 2^n

// 2의 거듭제곱으로 내림
uint32_t prev2 = std::bit_floor(v);

// 비트 너비 (log2 + 1)
int width = std::bit_width(v);       // 8 (0b1010_0110은 8비트 필요)

---

3. 비트마스크 플래그 패턴

enum class ItemFlags : uint32_t
{
    None      = 0,
    Stackable = 1 << 0,
    Equippable= 1 << 1,
    Quest     = 1 << 2,
    Tradeable = 1 << 3,
    Enchanted = 1 << 4,
};

// 비트 OR/AND/NOT 연산자 활성화
inline ItemFlags operator|(ItemFlags a, ItemFlags b)
{ return static_cast<ItemFlags>(uint32_t(a) | uint32_t(b)); }
inline ItemFlags operator&(ItemFlags a, ItemFlags b)
{ return static_cast<ItemFlags>(uint32_t(a) & uint32_t(b)); }
inline bool has(ItemFlags flags, ItemFlags flag)
{ return (flags & flag) != ItemFlags::None; }

ItemFlags sword = ItemFlags::Equippable | ItemFlags::Enchanted;
bool canEquip = has(sword, ItemFlags::Equippable); // true

---

4. std::bitset

#include <bitset>

std::bitset<64> visited; // 64개 방문 플래그

// 설정/해제/확인
visited.set(5);
visited.reset(5);
bool v = visited.test(5);

// 집합 연산
std::bitset<64> a(0xF0F0F0F0ULL);
std::bitset<64> b(0xFF00FF00ULL);
auto intersection = a & b;
auto union_set    = a | b;

// 순회: 설정된 비트
for (size_t i = 0; i < 64; ++i)
    if (visited.test(i))
        process(i);

// 카운트
std::cout << visited.count(); // SET 비트 수

---

5. 비트 트릭 — 실전 최적화

// 2의 거듭제곱으로 정렬된 크기로 올림 (버퍼 크기 계산)
size_t next_pow2(size_t n)
{
    return std::bit_ceil(n);
}

// XOR 스왑 (임시 변수 없이)
void xor_swap(int& a, int& b)
{
    if (&a != &b) { a ^= b; b ^= a; a ^= b; }
}

// 바이트 순서 반전 (endian swap)
uint32_t bswap(uint32_t v)
{
    return std::byteswap(v); // C++23
    // 또는: __builtin_bswap32(v) (GCC/Clang)
}

// n번째 SET 비트 위치 찾기
int nth_set_bit(uint64_t mask, int n)
{
    while (n--)
        mask &= mask - 1; // LSB 제거
    return std::countr_zero(mask);
}

---

6. 게임 개발 활용 — 컴포넌트 시스템

using ComponentMask = uint64_t;

constexpr ComponentMask TRANSFORM  = 1ULL << 0;
constexpr ComponentMask RIGID_BODY = 1ULL << 1;
constexpr ComponentMask RENDERER   = 1ULL << 2;
constexpr ComponentMask COLLIDER   = 1ULL << 3;

// 엔티티가 시스템 조건을 만족하는지 확인
bool matches_system(ComponentMask entity, ComponentMask required)
{
    return (entity & required) == required;
}

ComponentMask player = TRANSFORM | RIGID_BODY | RENDERER | COLLIDER;
ComponentMask physics_required = TRANSFORM | RIGID_BODY;

bool runs_physics = matches_system(player, physics_required); // true

---

7. 부호 없는 정수와 비트 조작 함정

// 주의: 부호 있는 정수의 시프트는 UB 위험
int x = -1;
int bad = x >> 1; // 구현 정의(implementation-defined) 동작
                   // 산술 시프트인지 논리 시프트인지 보장 없음

// 비트 조작에는 항상 부호 없는 타입 사용
uint32_t u = 0xFFFFFFFFu;
uint32_t safe = u >> 1; // 정의된 동작: 논리 시프트 (0x7FFFFFFF)

// 정수 리터럴에 u 접미사 필수
uint32_t flag = (1 << 31);  // 위험: int 오버플로 (UB)
uint32_t safe_flag = (1u << 31); // 안전: unsigned 리터럴

// 64비트 플래그
uint64_t big = (1ULL << 63); // 64비트 최상위 비트

---

8. 비트 필드(Bit Field) 활용

// 구조체 비트 필드: 좁은 정수를 패킹
struct Pixel {
    uint32_t r : 8;  // 8비트 (0~255)
    uint32_t g : 8;
    uint32_t b : 8;
    uint32_t a : 8;
};
// sizeof(Pixel) == 4

struct NetworkFlags {
    uint8_t syn : 1;
    uint8_t ack : 1;
    uint8_t fin : 1;
    uint8_t rst : 1;
    uint8_t     : 4; // 4비트 패딩
};
// sizeof(NetworkFlags) == 1

// 주의: 비트 필드는 포인터 연산 불가, 주소 취득 불가
// 성능 임계 코드에서는 수동 비트 조작이 더 빠를 수 있음

---

9. 체스/퍼즐 — 비트보드 패턴

비트보드(Bitboard)는 체스 같은 격자 게임에서 보드 상태를 비트로 표현하는 기법입니다.

// 체스 64칸을 uint64_t 하나로 표현
using Bitboard = uint64_t;

constexpr int sq(int rank, int file) { return rank * 8 + file; }

// 폰의 공격 가능 범위 (흰색 폰: 대각선 위)
Bitboard pawn_attacks_white(Bitboard pawns)
{
    return ((pawns << 7) & ~0x8080808080808080ULL) |  // 왼쪽 대각선
           ((pawns << 9) & ~0x0101010101010101ULL);   // 오른쪽 대각선
}

// 설정된 모든 비트(말 위치) 순회
void iterate_pieces(Bitboard board)
{
    while (board)
    {
        int sq = std::countr_zero(board); // 최하위 비트 위치
        process_piece(sq);
        board &= board - 1; // 최하위 비트 제거
    }
}

---

정리

C++20 <bit> 헤더로 popcount, countr_zero, rotl 등 이식 가능한 비트 유틸리티를 사용하세요. 비트마스크 플래그는 enum class로 타입 안전성을 보장하고, ECS 컴포넌트 마스크는 uint64_t 비트 연산으로 O(1) 쿼리를 구현하세요. 비트 조작 시 항상 부호 없는 타입(uint32_t, uint64_t)을 사용해 부호 있는 정수 시프트로 인한 미정의 동작을 피하세요.

기법	사용처
enum class + 비트 연산자	타입 안전 플래그
std::bitset<N>	고정 크기 비트 집합 연산
std::popcount	SET 비트 수 계산 (C++20)
std::countr_zero	LSB 위치 / 트레일링 제로
mask & (mask-1)	LSB 제거 루프 패턴
uint64_t 비트보드	격자 게임 상태 표현