[C++] 비트 연산자

비트 연산자(Bitwise Operators) 정리 및 활용 알고리즘

비트 연산자는 정수형 데이터를 비트 단위로 조작할 수 있는 연산자입니다. 이들은 빠르고 효율적인 연산이 가능하며, 다양한 알고리즘에 활용됩니다.

---

1. 비트 연산자 종류

연산자	이름	설명	예시
&	AND	대응되는 비트가 모두 1이면 1	5 & 3 = 1 (0101 & 0011 = 0001)
|	OR	대응되는 비트 중 하나라도 1이면 1	5 | 3 = 7 (0101	0011 = 0111)
^	XOR	대응되는 비트가 다르면 1	5 ^ 3 = 6 (0101 ^ 0011 = 0110)
~	NOT	모든 비트를 반전	~5 = -6 (2의 보수 체계 기준)
<<	왼쪽 시프트	비트를 왼쪽으로 이동, 오른쪽에 0 삽입	5 << 1 = 10 (0101 → 1010)
>>	오른쪽 시프트	비트를 오른쪽으로 이동, 왼쪽은 부호 유지	5 >> 1 = 2 (0101 → 0010)

---

2. 각 비트 연산자별 대표적인 알고리즘

2.1 & (AND)

활용: 짝수/홀수 판별

bool isEven(int x) {
    return (x & 1) == 0;
}

• 짝수는 마지막 비트가 0, 홀수는 1

활용: 비트 마스크 플래그 체크

if (flags & FLAG_WRITE) {
    // 쓰기 권한 있음
}

---

2.2 | (OR)

활용: 비트 마스크 설정

flags |= FLAG_READ;  // 읽기 권한 추가

• 특정 플래그를 켜는 데 사용됨

활용: 여러 조건을 합치는 경우

int combined = FLAG_A | FLAG_B;

---

2.3 ^ (XOR)

활용: 두 수를 임시 변수 없이 스왑하기

x = x ^ y;
y = x ^ y;
x = x ^ y;

활용: 한 번만 등장하는 원소 찾기

(모든 숫자가 두 번씩 등장하고 하나만 한 번 등장할 때)

int result = 0;
for (int num : nums) {
    result ^= num;
}
// result가 정답

---

2.4 ~ (NOT)

활용: 비트를 반전시키기

int inverted = ~x;

• 특정 비트를 제외한 나머지를 모두 반전시키고 싶을 때 유용

활용: 마스크 반전

flags &= ~FLAG_READ;  // 읽기 권한 제거

---

2.5 << (왼쪽 시프트)

활용: 2의 거듭제곱 곱셈

int x = 3;
int result = x << 2;  // x * 4

활용: 플래그 정의

const int FLAG_EXEC = 1 << 2;  // 00000100

---

2.6 >> (오른쪽 시프트)

활용: 2의 거듭제곱 나눗셈

int x = 8;
int result = x >> 1;  // x / 2

활용: 이진 탐색에서 중간값 계산 최적화

int mid = (low + high) >> 1;

---

3. 실용 예시: 플래그 마스크

const int FLAG_READ  = 1 << 0;  // 0001
const int FLAG_WRITE = 1 << 1;  // 0010
const int FLAG_EXEC  = 1 << 2;  // 0100

int permission = FLAG_READ | FLAG_WRITE;  // 0011

if (permission & FLAG_READ) {
    cout << "읽기 권한 있음";
}

---

https://www.acmicpc.net/source/98077739

가능한 조합 탐색

vector<int> v;
        v.clear();

        for (int j = 0; j < n; j++)
        {
            if (i & (1 << j))
            {
                for (int t = 0; t < 5; t++)
                {
                    sum[t] += input[j][t];
                }
                v.push_back(j);
            }
        }