비트 연산 실전: AND·OR·XOR·시프트, 비트마스크로 플래그·권한 관리, 알고리즘 문제

작성 0xmote · 2026년 5월 19일 · 32분 읽기 · 수정 2026년 9월 25일 초급 가이드

이 글의 핵심

bool 변수 여러 개로 관리하던 옵션을 정수 하나의 비트로 묶으면 저장 공간과 비교 연산이 단순해지지만, 마스크를 잘못 만들거나 음수를 시프트할 때 실수하기 쉽습니다. 이 글은 각 연산의 진리표에서 출발해 플래그 설정·해제·토글 패턴, XOR로 홀수 번 나온 수 찾기, 곱셈 대신 시프트를 쓸 때의 실제 효과까지 예제로 설명합니다.

들어가며

비트 연산은 비트 단위로 데이터를 조작하는 연산입니다. AND, OR, XOR, NOT, Shift 등이 있으며, CPU가 한 사이클 안팎에 처리하는 가장 기본적인 명령입니다. 비유로 말씀드리면, 비트 연산은 전구 스위치를 직접 조작하는 것입니다. 일반 연산이 “방 전체 밝기 조절”이라면, 비트 연산은 “각 전구를 개별적으로 켜고 끄는 것”입니다.

비트 연산이 “빠르다”는 설명은 절반만 맞습니다. 연산 자체가 빠른 것은 사실이지만, 현대 컴파일러는 x * 8을 알아서 x << 3으로, x % 2를 비트 연산으로 바꿔 주기 때문에 곱셈을 시프트로 손수 바꿔서 얻는 이득은 거의 없습니다. 비트 연산을 배워야 하는 진짜 이유는 속도가 아니라 표현력입니다. 여러 개의 참/거짓 상태를 정수 하나에 담고, 하드웨어 레지스터나 네트워크 패킷의 특정 비트를 읽고, 파일 권한이나 색상처럼 비트 단위로 정의된 데이터를 다루는 일은 비트 연산 없이는 할 수 없습니다. 이 글은 연산의 동작에서 시작해 이런 실전 용도와, 부호 있는 정수에서 생기는 함정까지 다룹니다.

기본 비트 연산

AND 연산 (&)

두 비트가 모두 1일 때만 1:

  1010  (10)
& 1100  (12)
------
  1000  (8)

진리표:

A	B	A & B
0	0	0
0	1	0
1	0	0
1	1	1

코드 예시:

int a = 10;  // 1010
int b = 12;  // 1100
int c = a & b;  // 1000 = 8
printf("%d\n", c);  // 8

실전 활용: 짝수 판별

// 일반 방법
bool isEven(int n) {
    return n % 2 == 0;
}
// 비트 연산 (최적화 빌드에서는 위와 같은 기계어가 나옴)
bool isEven(int n) {
    return (n & 1) == 0;  // 마지막 비트가 0이면 짝수
}

AND는 마스크로 원하는 비트만 남기는 연산입니다. n & 1은 마지막 비트만 남기고 나머지를 0으로 지우므로, 2의 0제곱 자리, 즉 홀짝을 알려 줍니다. 두 함수는 최적화를 켠 GCC나 Clang에서 같은 기계어로 컴파일되니 성능 때문에 고를 필요는 없고, 읽기 쉬운 쪽을 쓰면 됩니다. 다만 홀수 판별에서는 차이가 생깁니다. n % 2 == 1은 음수에서 틀립니다. C++에서 -3 % 2는 -1이기 때문입니다. (n & 1) == 1은 2의 보수 표현 덕분에 음수에서도 맞게 동작하고, n % 2 != 0도 안전합니다.

비트 연산자에는 우선순위 함정이 있습니다. &, |, ^는 ==보다 우선순위가 낮아서, if (n & 1 == 0)은 n & (1 == 0), 즉 n & 0으로 해석되어 항상 거짓입니다. GCC는 “suggest parentheses around comparison in operand of ’&’” 경고를 내지만 경고를 꺼 두었다면 조용히 틀린 결과가 나옵니다. 위 코드처럼 비트 연산은 항상 괄호로 감싸는 습관을 들이세요.

OR 연산 (|)

두 비트 중 하나라도 1이면 1:

  1010  (10)
| 1100  (12)
------
  1110  (14)

진리표:

A	B	A \| B
0	0	0
0	1	1
1	0	1
1	1	1

코드 예시:

int a = 10;  // 1010
int b = 12;  // 1100
int c = a | b;  // 1110 = 14
printf("%d\n", c);  // 14

XOR 연산 (^)

두 비트가 다르면 1:

  1010  (10)
^ 1100  (12)
------
  0110  (6)

진리표:

A	B	A ^ B
0	0	0
0	1	1
1	0	1
1	1	0

코드 예시:

int a = 10;  // 1010
int b = 12;  // 1100
int c = a ^ b;  // 0110 = 6
printf("%d\n", c);  // 6

실전 활용: 두 값 교환 (swap)

// 일반 방법
int a = 5, b = 10;
int temp = a;
a = b;
b = temp;
// 비트 연산 (temp 변수 불필요)
int a = 5, b = 10;
a = a ^ b;  // a = 5 ^ 10
b = a ^ b;  // b = (5 ^ 10) ^ 10 = 5
a = a ^ b;  // a = (5 ^ 10) ^ 5 = 10

XOR의 핵심 성질은 세 가지입니다. a ^ a = 0(같은 값끼리는 지워짐), a ^ 0 = a(0과는 그대로), 그리고 교환·결합 법칙이 성립한다는 것입니다. 그래서 a ^ b를 한 번 더 b와 XOR하면 b가 지워져 a가 돌아옵니다. XOR swap은 이 성질을 보여 주는 고전적인 예지만 실무에서 쓸 이유는 없습니다. 임시 변수를 쓰는 방식은 컴파일러가 레지스터만으로 처리해 더 빠르거나 같고, XOR swap은 세 연산이 앞의 결과에 의존해 CPU가 병렬로 실행하지 못합니다. 결정적인 함정도 있습니다. 두 변수가 같은 메모리를 가리키면(xorSwap(arr[i], arr[j])에서 i == j인 경우) 첫 줄에서 a ^ a = 0이 되어 값이 0으로 지워집니다. 값 교환은 std::swap을 쓰세요.

XOR이 실제로 유용한 곳은 “두 번 적용하면 원래대로 돌아오는” 성질이 필요한 곳입니다. 비트 토글(flags ^= FLAG), 체크섬과 패리티 계산, RAID 5의 패리티 복구, 뒤의 “홀수 번 나온 수 찾기” 문제가 모두 이 성질을 씁니다.

NOT 연산 (~)

모든 비트 반전:

  1010  (10)
~
------
  0101  (-11, 2의 보수)

코드 예시:

int a = 10;      // 00001010
int b = ~a;      // 11110101 = -11
printf("%d\n", b);  // -11

위 그림은 4비트나 8비트로 줄여 그린 것이고, 실제 int는 32비트라 ~10은 앞의 28개 0도 모두 1로 뒤집힙니다. 그래서 결과가 5가 아니라 -11입니다. 2의 보수 표현에서 ~x는 항상 -x - 1과 같다는 관계를 알아 두면 결과를 바로 계산할 수 있습니다. NOT이 실무에서 가장 많이 쓰이는 곳은 단독 연산보다 마스크 반전입니다. 아래 비트마스크 절의 flags &= ~WRITE처럼 “이 비트만 빼고 전부 1인 마스크”를 만들어 특정 비트를 지울 때 씁니다. 반대로 bool 값을 뒤집으려고 ~를 쓰는 것은 흔한 실수로, ~true는 ~1, 즉 -2가 되어 여전히 참입니다. 논리 부정은 !를 써야 합니다.

시프트 연산

왼쪽 시프트 (<<)

비트를 왼쪽으로 이동:

  0101  (5)
<< 1
------
  1010  (10)

효과: 2를 곱함

int a = 5;
int b = a << 1;  // 5 × 2 = 10
int c = a << 2;  // 5 × 4 = 20
int d = a << 3;  // 5 × 8 = 40
// 일반 공식: x << n = x × 2^n

오른쪽 시프트 (>>)

비트를 오른쪽으로 이동:

  1010  (10)
>> 1
------
  0101  (5)

효과: 2로 나눔

int a = 20;
int b = a >> 1;  // 20 ÷ 2 = 10
int c = a >> 2;  // 20 ÷ 4 = 5
int d = a >> 3;  // 20 ÷ 8 = 2
// 일반 공식: x >> n = x ÷ 2^n (0 이상의 정수에서, 나머지는 버림)

시프트가 곱셈·나눗셈과 같은 이유는 진법 글의 자릿값 원리 그대로입니다. 2진수에서 모든 비트를 왼쪽으로 한 칸 옮기면 각 비트의 무게가 두 배가 되니 전체 값도 두 배가 됩니다. 10진수에서 끝에 0을 붙이면 10배가 되는 것과 같습니다. 주의할 점은 공식이 0 이상의 값에서만 정확하다는 것입니다. 음수의 오른쪽 시프트는 음의 무한대 쪽으로 내림하고 /는 0 쪽으로 버림하므로 -7 >> 1은 -4, -7 / 2는 -3으로 결과가 다릅니다(FAQ 참고). 왼쪽 시프트는 비트가 밀려 나가면 값이 조용히 잘리므로, x << n이 타입 범위를 넘으면 곱셈 결과와 달라집니다.

성능 비교

// 곱셈
for (int i = 0; i < x; i++) {
    int y = i * 2;
}
// 시프트
for (int i = 0; i < x; i++) {
    int y = i << 1;
}
// 최적화 빌드(-O2)에서는 두 루프가 같은 기계어가 됨
// (결과를 쓰지 않으면 루프 자체가 통째로 제거되기도 함)

이런 비교 벤치마크를 직접 돌려 보면 결과가 들쭉날쭉하거나 0ms가 나오는 경우가 많습니다. 컴파일러가 i * 2를 이미 시프트나 lea 명령으로 바꾸고, y를 아무 데도 쓰지 않으면 루프 전체를 지워 버리기 때문입니다. 최적화를 끈(-O0) 빌드에서 측정한 차이는 실제 프로그램의 성능과 무관합니다. 그래서 “곱셈을 시프트로 바꾸면 빨라진다”는 조언은 오래된 컴파일러나 특수한 환경에서나 의미가 있었던 이야기이고, 오늘날에는 의미에 맞는 연산자를 쓰는 것이 정답입니다. 곱하는 의도라면 * 2, 비트를 옮기는 의도라면 << 1을 쓰세요.

비트마스크

플래그 관리

여러 불리언 값을 하나의 정수로 관리:

// 권한 플래그
const int READ    = 1 << 0;  // 0001 = 1
const int WRITE   = 1 << 1;  // 0010 = 2
const int EXECUTE = 1 << 2;  // 0100 = 4
const int DELETE  = 1 << 3;  // 1000 = 8
// 권한 설정
int permissions = 0;
permissions |= READ;     // 읽기 권한 추가
permissions |= WRITE;    // 쓰기 권한 추가
// permissions = 0011 = 3
// 권한 확인
if (permissions & READ) {
    printf("읽기 권한 있음\n");
}
// 권한 제거
permissions &= ~WRITE;  // 쓰기 권한 제거
// permissions = 0001 = 1
// 권한 토글
permissions ^= EXECUTE;  // 실행 권한 토글

비트 플래그 패턴

// 플래그 설정
flags |= FLAG;
// 플래그 해제
flags &= ~FLAG;
// 플래그 토글
flags ^= FLAG;
// 플래그 확인
if (flags & FLAG) { /* ... */ }
// 여러 플래그 한 번에 설정
flags |= (FLAG1 | FLAG2 | FLAG3);
// 여러 플래그 한 번에 확인
if ((flags & (FLAG1 | FLAG2)) == (FLAG1 | FLAG2)) {
    // FLAG1과 FLAG2 모두 설정됨
}

각 플래그를 1 << n으로 정의하는 이유는 플래그마다 서로 다른 비트 하나만 1이 되게 하기 위해서입니다. 그래야 OR로 합쳐도 서로 겹치지 않고, AND로 각각을 따로 꺼낼 수 있습니다. 실수로 const int DELETE = 3;처럼 2의 거듭제곱이 아닌 값을 넣으면 READ와 WRITE를 합친 것과 같은 비트가 되어, DELETE를 확인하면 읽기·쓰기 권한만 있는 사용자도 통과합니다.

마지막 두 패턴의 차이도 중요합니다. flags & (FLAG1 | FLAG2)만 검사하면 둘 중 하나라도 있으면 참이 됩니다. “모두 있는가”를 확인하려면 결과가 마스크 자체와 같은지 비교해야 합니다. 권한 검사에서 이 둘을 혼동하면 쓰기 권한 없이 읽기 권한만 있는 사용자가 “읽기+쓰기가 필요한” 작업을 통과하는 보안 버그가 됩니다.

C++에서 플래그를 이렇게 int 상수로 두면 서로 무관한 정수와도 섞여 버리므로, enum class에 |, & 연산자를 오버로드하거나 std::bitset<N>을 쓰면 타입 안전성을 얻을 수 있습니다. bitset은 set(), reset(), test(), count()처럼 의도가 드러나는 메서드를 제공하고, 범위를 벗어난 비트에 접근하면 std::out_of_range 예외를 던져 실수를 잡아 줍니다(단 test()와 set()은 검사하지만 operator[]는 검사하지 않습니다).

비트마스크를 DB 컬럼이나 API 응답에 저장하기 시작하면 규칙이 하나 더 생깁니다. 한 번 배정한 비트 위치는 절대 바꾸거나 재사용하면 안 됩니다. 중간 플래그 하나를 지우면서 뒤의 상수들을 한 칸씩 당기면, 이미 저장된 값들의 의미가 한꺼번에 바뀌어 기존 사용자의 권한이 엉뚱하게 해석됩니다. 비트마스크를 처음 설계할 때 흔히 저지르는 실수가 이것이고, 그래서 폐기한 플래그는 주석으로 “예약됨”이라고 남겨 두고 새 플래그는 항상 뒤쪽 비트에 추가하는 편이 안전합니다. 또 SQL에서 “쓰기 권한이 있는 사용자”를 찾으려면 WHERE permissions & 2 <> 0처럼 조건을 써야 하는데, 이런 조건은 일반 인덱스를 타지 못해 전체 스캔이 됩니다. 플래그로 자주 검색해야 한다면 별도 컬럼이나 연결 테이블이 더 나은 선택입니다.

실전 활용

Unix 파일 권한

// rwxr-xr-x = 755 (오른쪽 주석은 8진수 값)
const int OWNER_READ    = 1 << 8;  // 0400
const int OWNER_WRITE   = 1 << 7;  // 0200
const int OWNER_EXECUTE = 1 << 6;  // 0100
const int GROUP_READ    = 1 << 5;  // 0040
const int GROUP_EXECUTE = 1 << 3;  // 0010
const int OTHER_READ    = 1 << 2;  // 0004
const int OTHER_EXECUTE = 1 << 0;  // 0001
int mode = OWNER_READ | OWNER_WRITE | OWNER_EXECUTE |
           GROUP_READ | GROUP_EXECUTE |
           OTHER_READ | OTHER_EXECUTE;
// mode = 0755 (8진수)

Unix 권한은 9개의 비트를 3개씩 세 묶음(소유자·그룹·기타)으로 나눈 비트마스크입니다. 그래서 8진수 한 자리가 한 묶음과 정확히 맞아떨어집니다. 실제 코드에서는 이 상수를 직접 정의하지 않고 <sys/stat.h>의 S_IRUSR, S_IWUSR, S_IXUSR, S_IRGRP 등을 씁니다. 파일의 현재 권한에서 그룹 쓰기 권한만 빼는 것도 앞의 패턴 그대로 mode & ~S_IWGRP이며, 셸의 umask 022가 새 파일 권한에서 그룹·기타의 쓰기 비트를 빼는 것도 같은 원리입니다.

RGB 색상 처리

// RGB 색상: 0xRRGGBB
int color = 0xFF5733;  // 빨강=FF, 초록=57, 파랑=33
// 각 채널 추출
int red   = (color >> 16) & 0xFF;  // FF = 255
int green = (color >> 8) & 0xFF;   // 57 = 87
int blue  = color & 0xFF;          // 33 = 51
// 색상 합성
int newColor = (red << 16) | (green << 8) | blue;

IP 주소 처리

// IP: 192.168.1.1
int ip = (192 << 24) | (168 << 16) | (1 << 8) | 1;
// ip = 0xC0A80101
// 각 옥텟 추출
int octet1 = (ip >> 24) & 0xFF;  // 192
int octet2 = (ip >> 16) & 0xFF;  // 168
int octet3 = (ip >> 8) & 0xFF;   // 1
int octet4 = ip & 0xFF;          // 1

색상과 IP 주소는 같은 패턴입니다. 조립할 때는 각 바이트를 제자리로 밀어 올린 뒤 OR로 합치고, 분해할 때는 원하는 바이트를 맨 아래로 끌어내린 뒤 & 0xFF로 나머지를 지웁니다. & 0xFF를 빼먹으면 위쪽 바이트가 함께 남아 (ip >> 16)이 168이 아니라 0xC0A8(49320)이 됩니다.

이 IP 예제에는 타입 문제가 숨어 있습니다. 192 << 24는 약 32억으로 int의 최댓값(약 21억)을 넘으므로 결과가 음수가 됩니다(C++20 이전에는 구현에 따라 동작이 달랐습니다). 이후 ip >> 24는 음수의 산술 시프트라 부호 비트가 채워져 0xFFFFFFC0이 되는데, 마침 & 0xFF가 위쪽을 지워 줘서 결과가 우연히 맞을 뿐입니다. IP 주소처럼 32비트를 꽉 채우는 값은 uint32_t로 다루는 것이 원칙이고, 네트워크로 보낼 때는 바이트 순서(엔디언)도 htonl로 맞춰야 합니다.

비트 카운팅

// 1의 개수 세기 (Population Count)
// 매개변수를 unsigned로: int 음수는 >>에서 부호 비트가 채워져 무한 루프
int countBits(unsigned int n) {
    int count = 0;
    while (n) {
        count += n & 1;  // 마지막 비트 확인
        n >>= 1;         // 오른쪽으로 1비트 시프트
    }
    return count;
}
// 예시
countBits(13);  // 1101 → 3개
// C++20: std::popcount
#include <bit>
int count = std::popcount(13u);  // 3 (unsigned 타입만 받음)

countBits의 매개변수를 int로 두면 음수를 넣었을 때 무한 루프에 빠집니다. 음수의 >>는 부호 비트(1)를 왼쪽에 계속 채우므로 n이 0이 되지 않고 -1에서 멈춰 버립니다. 비트를 세는 함수는 부호 없는 타입으로 받아야 합니다. 루프를 줄이는 고전적인 방법으로 n &= n - 1이 있는데, 이 연산은 가장 낮은 1비트 하나를 지우므로 1의 개수만큼만 반복합니다. 다음 절의 “2의 거듭제곱 판별”이 이 성질을 이용합니다.

실무에서는 직접 구현할 필요가 없습니다. C++20의 std::popcount는 대부분의 CPU에 있는 popcnt 명령 하나로 컴파일되고, C++20 이전이라면 GCC·Clang의 __builtin_popcount, MSVC의 __popcnt를 씁니다. std::popcount는 부호 없는 정수만 받도록 설계되어 있어서, std::popcount(13)처럼 int를 넘기면 “no matching function for call to ‘popcount(int)’” 에러가 납니다. 음수의 비트 패턴에 대한 혼란을 원천적으로 막으려는 설계입니다.

알고리즘 문제

문제 1: 두 수의 합 (비트 연산)

// 덧셈을 비트 연산으로 구현
int add(int a, int b) {
    while (b != 0) {
        int carry = a & b;     // 캐리 계산
        a = a ^ b;             // 합 계산 (캐리 제외)
        b = carry << 1;        // 캐리를 왼쪽으로
    }
    return a;
}
// 예시
add(5, 3);  // 8

이 코드는 CPU의 덧셈 회로(전가산기)가 하는 일을 소프트웨어로 흉내 낸 것입니다. XOR은 “올림을 무시한 자릿수별 합”(1+1=0, 1+0=1)이고, AND는 “양쪽이 모두 1이라 올림이 생기는 자리”입니다. 올림은 한 자리 위로 가야 하므로 << 1로 밀고, 올림이 더 이상 없을 때까지 반복합니다. 5(101) + 3(011)이라면 첫 바퀴에 합 110, 올림 010, 두 번째 바퀴에 합 100, 올림 100, 세 번째 바퀴에 합 000, 올림 1000, 마지막에 합 1000(8)이 됩니다. 코딩 테스트에서 ”+ 연산자 없이 덧셈하기” 문제로 나오지만 실무에서 쓸 일은 없습니다. 음수가 섞이면 carry << 1이 음수의 왼쪽 시프트가 되어 C++20 이전에는 미정의 동작이었으므로, 이 문제를 C++로 풀 때는 unsigned로 계산하는 편이 안전합니다.

문제 2: 홀수 찾기 (XOR)

문제: 배열에서 홀수 개 나타나는 수 찾기

// 예시: [1, 2, 3, 2, 1] → 3 (3만 1개)
int findOdd(vector<int>& arr) {
    int result = 0;
    for (int num : arr) {
        result ^= num;  // XOR의 성질: a ^ a = 0
    }
    return result;
}
// 원리
// 1 ^ 2 ^ 3 ^ 2 ^ 1
// = (1 ^ 1) ^ (2 ^ 2) ^ 3
// = 0 ^ 0 ^ 3
// = 3

XOR의 교환·결합 법칙 덕분에 원소의 순서와 상관없이 짝을 이루는 값들이 서로 지워지고, 홀수 번 나온 값만 남습니다. 해시맵으로 개수를 세는 방법은 O(n) 추가 메모리가 필요하지만, 이 방법은 변수 하나로 끝납니다. 대신 전제 조건이 엄격해서 “정확히 하나만 홀수 번 나온다”가 보장될 때만 정답이 됩니다. 홀수 번 나온 수가 둘이면 두 수의 XOR이 나오고, 모든 수가 짝수 번 나오면 0이 나오는데 0이 실제 답인지 구분할 수 없습니다. 문제의 조건을 먼저 확인하세요.

문제 3: 2의 거듭제곱 판별

// n이 2의 거듭제곱인지 확인
bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}
// 원리
// 8 = 1000
// 7 = 0111
// 8 & 7 = 0000 = 0 (2의 거듭제곱)
// 6 = 0110
// 5 = 0101
// 6 & 5 = 0100 ≠ 0 (2의 거듭제곱 아님)

2의 거듭제곱은 2진수로 1이 정확히 하나인 수입니다. n - 1을 하면 그 1이 0이 되고 아래 자리가 모두 1로 바뀌므로(1000 → 0111), 둘을 AND하면 0이 됩니다. 1이 두 개 이상이면 가장 높은 1은 n - 1에서도 살아남아 AND 결과가 0이 아닙니다. n > 0 조건을 빼면 n = 0일 때 0 & -1 = 0이 되어 0을 2의 거듭제곱으로 잘못 판정하므로 반드시 필요합니다. C++20에서는 std::has_single_bit(n)이 같은 일을 하며, 메모리 할당기나 해시 테이블처럼 크기를 2의 거듭제곱으로 맞추는 코드에서 자주 쓰입니다. 크기가 2의 거듭제곱이면 index % size 대신 index & (size - 1)로 나머지를 구할 수 있기 때문입니다.

문제 4: 비트 반전

// n번째 비트 반전
int flipBit(int num, int n) {
    return num ^ (1 << n);
}
// 예시
flipBit(10, 0);  // 1010 → 1011 = 11
flipBit(10, 1);  // 1010 → 1000 = 8

flipBit은 앞의 비트 플래그 패턴 중 “토글”을 함수로 만든 것입니다. 1 << n으로 n번째 비트만 1인 마스크를 만들고 XOR하면 그 비트만 뒤집히고 나머지는 그대로입니다. 같은 모양으로 num | (1 << n)은 켜기, num & ~(1 << n)은 끄기, (num >> n) & 1은 읽기가 됩니다. 이 네 줄이 비트 조작 문제의 거의 전부라고 해도 과장이 아닙니다. 다만 n이 31이면 1 << 31, 32 이상이면 미정의 동작이라는 아래 트러블슈팅의 문제가 그대로 적용되므로, n이 외부 입력이라면 범위를 먼저 검사하거나 1U << n에 n < 32 조건을 붙여야 합니다.

성능 비교

곱셈 vs 시프트

// 일반 곱셈
for (int i = 0; i < x; i++) {
    int y = i * 8;
}
// 시프트 연산
for (int i = 0; i < x; i++) {
    int y = i << 3;  // × 8
}
// -O2에서는 i * 8도 시프트 명령으로 컴파일됨 → 차이 없음

나눗셈 vs 시프트

// 일반 나눗셈
for (int i = 0; i < x; i++) {
    int y = i / 4;
}
// 시프트 연산
for (int i = 0; i < x; i++) {
    int y = i >> 2;  // ÷ 4
}
// 상수 2의 거듭제곱 나눗셈도 컴파일러가 시프트로 바꿈
// 단, 부호 있는 int는 음수 처리를 위해 보정 명령이 몇 개 추가됨

곱셈과 나눗셈의 경우는 조금 다릅니다. 정수 곱셈은 현대 CPU에서 몇 사이클이면 끝나고 상수 곱셈은 컴파일러가 시프트로 바꾸므로 차이가 없지만, 나눗셈은 실제로 느린 연산(수십 사이클)입니다. 그래서 컴파일러는 i / 4처럼 상수로 나누는 경우 시프트나 곱셈으로 바꿔 줍니다. 부호 있는 int라면 -7 / 4가 -1이 되도록(0 쪽 버림) 보정 명령을 몇 개 끼워 넣는데, unsigned나 >>를 쓰면 이 보정이 없어져 아주 약간 짧아집니다. 반면 변수로 나누는 i / n은 컴파일러가 바꿀 수 없어 진짜 나눗셈 명령이 실행됩니다. 이런 경우 n이 항상 2의 거듭제곱이라는 것을 프로그래머가 알고 있다면 i >> log2(n)이나 i & (n - 1)로 바꾸는 최적화가 의미 있습니다. 해시 테이블 크기를 2의 거듭제곱으로 잡는 이유가 이것입니다.

플래그 vs bool 배열

// bool 배열 (메모리 많이 사용)
bool flags[32];  // 32 Bytes
// 비트 플래그 (메모리 적게 사용)
int flags = 0;   // 4 Bytes (8배 절약)

메모리 절약은 플래그가 많은 객체에 반복될 때 의미가 있습니다. 객체 하나에 bool 5개를 두면 구조체 정렬 때문에 생각보다 많은 공간을 차지할 수 있고, 이런 객체가 수백만 개라면 캐시 효율까지 차이가 납니다. 한편 비트로 압축하면 특정 플래그 하나를 읽고 쓸 때마다 마스크 연산이 필요하고, 여러 스레드가 같은 정수의 서로 다른 비트를 동시에 수정하면 데이터 레이스가 됩니다. bool 배열의 원소는 각자 다른 메모리 위치라 이런 문제가 없습니다. 플래그를 스레드 간에 공유한다면 std::atomic<uint32_t>의 fetch_or, fetch_and를 써야 합니다.

트러블슈팅

음수 시프트 문제

문제:

int a = -8;  // 11111000 (2의 보수)
int b = a >> 1;  // 결과는?

원인:

산술 시프트 (Arithmetic Shift): 부호 비트 유지
논리 시프트 (Logical Shift): 0으로 채움 해결:

// 부호 없는 정수 사용
unsigned int a = -8;
unsigned int b = a >> 1;  // 논리 시프트

여기서 “해결”의 의미를 정확히 알아 둘 필요가 있습니다. unsigned int a = -8;은 -8의 비트 패턴을 그대로 부호 없는 값으로 읽으므로 a는 4294967288이 되고, a >> 1은 2147483644입니다. 즉 unsigned로 바꾸면 결과가 -4가 아니라 완전히 다른 큰 양수가 됩니다. 이 방법은 “값을 2로 나누는” 문제가 아니라 “비트 패턴을 오른쪽으로 옮기는” 문제를 풀 때만 맞는 해결책입니다. 음수를 2로 나눈 값이 필요하다면 그냥 / 2를 쓰는 것이 정답입니다.

언어마다 이 부분의 규칙이 다르다는 점도 헷갈리기 쉽습니다. Java와 JavaScript에는 부호 없는 타입 대신 논리 시프트 전용 연산자 >>> 가 있어서 -8 >>> 1로 0을 채우는 시프트를 합니다. JavaScript는 비트 연산을 할 때 숫자를 32비트 정수로 변환하므로 2 ** 32 | 0이 0이 되고, 53비트를 넘는 값의 비트 연산에는 BigInt를 써야 합니다. Python의 정수는 크기 제한이 없어서 ~10은 -11로 같지만 1 << 100도 정상적인 값이며, 32비트로 잘린 결과가 필요하면 & 0xFFFFFFFF로 직접 잘라야 합니다. C++ 코드를 다른 언어로 옮길 때 해시 함수나 체크섬 결과가 달라진다면 대개 이 차이 때문입니다.

오버플로우

문제:

int a = 1 << 31;  // 오버플로우!
// int는 32비트, 최상위 비트는 부호 비트

1 << 31의 결과는 언어와 표준 버전에 따라 다릅니다. C에서는 부호 있는 정수가 표현할 수 없는 값으로 시프트되므로 미정의 동작이고, C++14~17에서는 값이 INT_MIN으로 변환되는 구현 정의 동작, C++20부터는 2의 보수가 표준화되어 INT_MIN(-2147483648)으로 정해졌습니다. 어느 경우든 “31번 비트를 켠 마스크”를 의도했다면 부호 있는 타입을 쓸 이유가 없습니다. 리터럴 1은 int라서 1 << 31, 1 << 40 모두 int 기준으로 계산된다는 점이 핵심으로, 결과를 long long 변수에 담아도 이미 계산이 끝난 뒤라 소용없습니다. 시프트할 왼쪽 피연산자의 타입을 1U, 1ULL처럼 먼저 넓혀야 합니다. 해결:

// unsigned 사용
unsigned int a = 1U << 31;  // OK
// 또는 long long 사용
long long a = 1LL << 31;  // OK

비트마스크 실수

문제:

int flags = 0;
flags |= 1 << 32;  // Undefined Behavior!
// int는 32비트, 32비트 시프트는 UB

해결:

// 64비트 사용
long long flags = 0;
flags |= 1LL << 32;  // OK

타입의 비트 수 이상으로 시프트하는 것(int에 << 32)은 C와 C++ 모두에서 명확한 미정의 동작이고, 결과가 CPU마다 다르게 나오는 대표적인 예입니다. x86은 시프트 횟수의 하위 5비트만 사용해 1 << 32를 1 << 0, 즉 1로 계산하는 반면, 다른 아키텍처는 0을 내기도 합니다. 그래서 “내 PC에서는 1이 나왔다”는 식으로 동작을 추론하면 안 됩니다. 시프트 횟수가 변수라면 특히 위험한데, 비트마스크 DP에서 원소가 32개를 넘는 입력을 받는 순간 1 << n이 조용히 틀린 마스크를 만들어 오답이 납니다. 플래그가 32개를 넘을 가능성이 있다면 처음부터 uint64_t나 std::bitset을 쓰세요. 더 깊은 알고리즘 활용은 알고리즘에서 쓰는 비트 연산 글에서 다룹니다.

마무리

비트 연산은 여러 상태를 정수 하나에 담고, 비트 단위로 정의된 데이터를 정확히 읽고 쓰기 위한 도구입니다.

핵심 요약:

연산	기호	용도
AND	&	비트 마스킹, 짝수 판별
OR	\|	플래그 설정
XOR	^	토글, 암호화, 중복 찾기
NOT	~	비트 반전
왼쪽 시프트	<<	비트를 제자리로 밀어 조립, 마스크 생성
오른쪽 시프트	>>	원하는 필드를 아래로 끌어내려 추출

실전 활용:

플래그 관리 (권한, 설정)
비트 단위 데이터 조립·분해 (색상, IP, 패킷 헤더, 하드웨어 레지스터)
알고리즘 문제 (XOR, 비트 카운팅, 비트마스크 DP)
체크섬과 패리티

다음 단계:

비트 연산은 속도를 위한 기교보다, 비트 단위로 정의된 데이터를 정확히 다루기 위한 도구로 익혀 두는 편이 실무에서 훨씬 쓸모가 있습니다.

자주 묻는 질문 (FAQ)

Q. 음수를 오른쪽으로 시프트하면 결과가 어떻게 되나요?

A. -8 >> 1처럼 부호 있는 음수를 오른쪽으로 시프트하면 대부분의 컴파일러는 부호 비트를 채우는 산술 시프트를 해서 -4가 나오지만, C++20 이전에는 이 동작이 구현 정의였습니다. 또한 음수의 >> 1은 0 방향 버림인 /2와 달리 음의 무한대 방향으로 내림하므로 -7 >> 1은 -3이 아니라 -4가 됩니다. 비트 패턴 자체를 다루는 코드라면 unsigned 타입으로 바꿔 논리 시프트를 하는 것이 안전합니다.

이 글의 핵심

들어가며

기본 비트 연산

AND 연산 (&)

OR 연산 (|)

XOR 연산 (^)

NOT 연산 (~)

시프트 연산

왼쪽 시프트 (<<)

오른쪽 시프트 (>>)

성능 비교

비트마스크

플래그 관리

비트 플래그 패턴

실전 활용

Unix 파일 권한

RGB 색상 처리

IP 주소 처리

비트 카운팅

알고리즘 문제

문제 1: 두 수의 합 (비트 연산)

문제 2: 홀수 찾기 (XOR)

문제 3: 2의 거듭제곱 판별

문제 4: 비트 반전

성능 비교

곱셈 vs 시프트

나눗셈 vs 시프트

플래그 vs bool 배열

트러블슈팅

음수 시프트 문제

오버플로우

비트마스크 실수

마무리

자주 묻는 질문 (FAQ)

Q. 음수를 오른쪽으로 시프트하면 결과가 어떻게 되나요?

같이 보면 좋은 글