[C++] Bit Operation 활용

문제

N개의 수가 주어지며, N은 짝수이다.
2개의 수 A, B (A < B)를 제외하고, 서로 같은 수가 반드시 짝수 개 있음이 보장된다.
A, B는 각각 홀수 개 존재함이 보장된다.

첫째 줄에 N이 주어지며, 그 다음 줄에 N개의 수가 주어진다.
A, B를 출력하라. ( O <= N <= 1,000,000) 주어지는 모든 수는 32비트 정수형이다.

<예제>

입력 10 1 5 4 1 8 5 5 5 7 4 출력 7 8

---

#include <iostream>
using namespace std;
int arr[10];
int N;

void func()
{
    int size = N;

int s = arr[0]; // 배열 첫 번째 요소를 s에 저장
int a = 0; // 홀수 번 등장하는 요소 중 작은 것을 저장할 변수
int b = 0; // 홀수 번 등장하는 요소 중 큰 것을 저장할 변수

// XOR을 이용한 중복되지 않는 홀수 번 등장하는 요소의 XOR 연산
for (int i = 1; i < size; i++)
    s ^= arr[i];

// 홀수 번 등장하는 요소를 찾기 위해 s에서 가장 오른쪽 비트 1을 추출
int bitnum = s & ~(s - 1);

// bitnum의 가장 오른쪽 비트가 1인 요소와 0인 요소를 나누어 XOR 연산을 수행
for (int i = 0; i < size; i++)
{
    if (arr[i] & bitnum)
        a ^= arr[i];
    else
        b ^= arr[i];
}

// a가 b보다 작은 경우 a와 b를 출력하고 그렇지 않으면 b와 a를 출력
if (a < b)
    cout << a << " " << b;
else
    cout << b << " " << a;
}

int main() {
    cin >> N;

for (int i = 0; i < N; i++)
    cin >> arr[i];

func(); // 배열에서 홀수 번 등장하는 두 요소를 찾아 출력하는 함수 func() 호출
}

 

 

 

 

---

 

 

// 비트 연산 언제 쓰는데? 
    // #1. 문제가 노골적인 비트연산 문제이다
    // #2. (비트 관련문제) 비트마스킹 (bit masking)
    
    // Bitmasking #1
    // 특정 비트를 바꾸는 방법
    // B = 5 => 0101
    // 문제 : 특정 비트를 1로 바꾸고 싶다. 
    // N = 1 => 0111 => 7

    //    0101
    //    0010
    // | ------
    //    0111
    int N = 1; 
    int res = B | (1 << N);
    cout << res << '\\n';

    // Bitmasking #2 
    // 특정 bit를 토글 -> 내가 정한 위치를 바꾸는겁니다.
    // B = 5 => 0101
    // N = 1 => 0111
    // N = 0 => 0100 

    //    0101
    //    0010
    // ^ ------
    //    0101
    N = 2;
    res = B ^ (1 << N);
    cout << res << '\\n';

    // Bitmasking #2 
    // 특정 bit를 삭제
    // B = 5 => 0101
    // N = 0 => 0100
    // N = 2 => 0001
    // N = 1 => 0101

    //    0101
    //    1011
    // & ------
    //    0001
    N = 2;
    res = B & ~(1 << N);
    cout << res << '\\n';
}