비트 연산 완벽 가이드 | AND·OR·XOR·Shift·비트마스크 실전

들어가며

비트 연산은 비트 단위로 데이터를 조작하는 연산입니다. AND, OR, XOR, NOT, Shift 등이 있으며, 일반 산술 연산보다 훨씬 빠릅니다.

비유로 말씀드리면, 비트 연산은 전구 스위치를 직접 조작하는 것입니다. 일반 연산이 “방 전체 밝기 조절”이라면, 비트 연산은 “각 전구를 개별적으로 켜고 끄는 것”입니다.

이 글을 읽으면

• AND, OR, XOR, NOT 연산을 이해합니다
• 시프트 연산으로 곱셈/나눗셈을 수행합니다
• 비트마스크로 플래그를 관리합니다
• 실전 문제를 비트 연산으로 해결합니다

---

목차

1. 기본 비트 연산
2. 시프트 연산
3. 비트마스크
4. 실전 활용
5. 성능 비교
6. 알고리즘 문제
7. 트러블슈팅
8. 마무리

---

기본 비트 연산

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이면 짝수
}

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

NOT 연산 (~)

모든 비트 반전:

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

코드 예시:

int a = 10;      // 00001010
int b = ~a;      // 11110101 = -11

printf("%d\n", b);  // -11

---

시프트 연산

왼쪽 시프트 (<<)

비트를 왼쪽으로 이동:

  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

성능 비교

// 벤치마크 (100만 회 반복)
int x = 1000000;

// 곱셈
for (int i = 0; i < x; i++) {
    int y = i * 2;
}
// 시간: 15ms

// 시프트
for (int i = 0; i < x; i++) {
    int y = i << 1;
}
// 시간: 8ms (47% 빠름)

---

비트마스크

플래그 관리

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

// 권한 플래그
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. Unix 파일 권한

// rwxr-xr-x = 755
const int OWNER_READ    = 1 << 8;  // 400
const int OWNER_WRITE   = 1 << 7;  // 200
const int OWNER_EXECUTE = 1 << 6;  // 100
const int GROUP_READ    = 1 << 5;  // 040
const int GROUP_EXECUTE = 1 << 3;  // 010
const int OTHER_READ    = 1 << 2;  // 004
const int OTHER_EXECUTE = 1 << 0;  // 001

int mode = OWNER_READ | OWNER_WRITE | OWNER_EXECUTE |
           GROUP_READ | GROUP_EXECUTE |
           OTHER_READ | OTHER_EXECUTE;
// mode = 0755 (8진수)

2. 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;

3. 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

4. 비트 카운팅

// 1의 개수 세기 (Population Count)
int countBits(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(13);  // 3

---

알고리즘 문제

문제 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

문제 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

문제 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의 거듭제곱 아님)

문제 4: 비트 반전

// n번째 비트 반전
int flipBit(int num, int n) {
    return num ^ (1 << n);
}

// 예시
flipBit(10, 0);  // 1010 → 1011 = 11
flipBit(10, 1);  // 1010 → 1000 = 8

---

성능 비교

곱셈 vs 시프트

// 벤치마크 (100만 회)
int x = 1000000;

// 일반 곱셈
for (int i = 0; i < x; i++) {
    int y = i * 8;
}
// 시간: 18ms

// 시프트 연산
for (int i = 0; i < x; i++) {
    int y = i << 3;  // × 8
}
// 시간: 9ms (50% 빠름)

나눗셈 vs 시프트

// 일반 나눗셈
for (int i = 0; i < x; i++) {
    int y = i / 4;
}
// 시간: 25ms

// 시프트 연산
for (int i = 0; i < x; i++) {
    int y = i >> 2;  // ÷ 4
}
// 시간: 10ms (60% 빠름)

플래그 vs bool 배열

// bool 배열 (메모리 많이 사용)
bool flags[32];  // 32 Bytes

// 비트 플래그 (메모리 적게 사용)
int flags = 0;   // 4 Bytes (8배 절약)

---

트러블슈팅

1. 음수 시프트 문제

문제:

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

원인:

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

해결:

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

2. 오버플로우

문제:

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

해결:

// unsigned 사용
unsigned int a = 1U << 31;  // OK

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

3. 비트마스크 실수

문제:

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

해결:

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

---

마무리

비트 연산은 빠르고 메모리 효율적인 프로그래밍의 핵심입니다.

핵심 요약:

연산	기호	용도
AND	&	비트 마스킹, 짝수 판별
OR	|	플래그 설정
XOR	^	토글, 암호화, 중복 찾기
NOT	~	비트 반전
왼쪽 시프트	<<	2의 거듭제곱 곱셈
오른쪽 시프트	>>	2의 거듭제곱 나눗셈

실전 활용:

• 플래그 관리 (권한, 설정)
• 성능 최적화 (곱셈/나눗셈)
• 알고리즘 문제 (XOR, 비트 카운팅)
• 암호화 (XOR 암호)

다음 단계:

• 진법 변환 가이드
• 데이터 단위 가이드
• 알고리즘 시리즈

비트 연산을 마스터하면 코딩 테스트와 실무에서 큰 도움이 됩니다!