1. 나의 시도

1.1. bitset 이용

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

const int n = 10;

std::bitset<n> a(5);
std::bitset<n> b(10);

for (int i = 0; i < n; ++i)
{
	// bit가 다르면 a[i]와 b[i]를 flip
	if (a[i] != b[i])
	{
		a[i] = !a[i];
		b[i] = !b[i];
	}
}
  • bitset은 비트 개수를 템플릿 인자로 받는 C++의 비트열 자료구조
  • bit의 비교 횟수는 비트열의 bit 개수 $N$에 비례한다 → 시간 복잡도: $O(N)$

1.2. shift 연산과 xor 연산 활용

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int a = 5;
int b = 10;

for (int i = 0; i < sizeof(int) * 8; ++i)
{
	// a와 b의 같은 자리의 bit를 비교 후 다르면 각 bit를 flip
	if ((a & (1 << i)) ^ (b & (1 << i)))
	{
		a ^= (1 << i);
		b ^= (1 << i);
	}
}
  • shift 연산은 대부분 프로세서에서 상수 시간에 계산
  • bit의 비교 횟수는 비교 데이터의 bit 개수 $N$에 비례 → 시간 복잡도: $O(N)$

2. 검색 후 찾은 방법

2.1. 덧셈, 뺄셈 활용

1
2
3
4
5
6
7
8
9

int a = x;
int b = y;

// a = x + y, b = y
a += b;
// a = x + y, b = x + y - y => x
b = a - b;
// a = x + y - x => y, b = x
a -= b;
  • 세 번의 산술 연산만 필요 → 시간 복잡도: $O(1)$
  • 오버플로우 위험 존재

2.2. 곰셉, 나눗셈 활용

1
2
3
4
5
6
7
8
9

int a = x;
int b = y;

// a = x * y, b = y
a *= b;
// a = x * y, b = x * y / y => x
b = a / b;
// a = x * y / x => y, b = x
a /= b;
  • 세 번의 산술 연산만 필요 → 시간 복잡도: $O(1)$
  • 오버플로우 위험 존재
  • 0 나누기 위험 존재

2.3. XOR 비트 연산 활용

1
2
3
4
5
6
7
8
9

int a = x;
int b = y;

// a = x ^ y, b = y
a ^= b;
// a = x ^ y, b = y ^ x ^ y => x
b ^= a;
// a = x ^ y ^ x => y, b = x
a ^= b;
  • 같은 데이터로 xor 연산 두 번하면 원래 데이터로 돌아오는 성질 이용
  • 세 번의 비트 연산만 필요 → 시간 복잡도: $O(1)$