1. 나의 시도
1.1. bitset 이용
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];
}
}
C++
복사
•
bitset은 비트 개수를 템플릿 인자로 받는 C++의 비트열 자료구조
•
bit의 비교 횟수는 비트열의 bit 개수 에 비례한다 → 시간 복잡도:
1.2. shift 연산과 xor 연산 활용
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);
}
}
C++
복사
•
shift 연산은 대부분 프로세서에서 상수 시간에 계산
•
bit의 비교 횟수는 비교 데이터의 bit 개수 에 비례 → 시간 복잡도:
2. 검색 후 찾은 방법
2.1. 덧셈, 뺄셈 활용
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;
C++
복사
•
세 번의 산술 연산만 필요 → 시간 복잡도:
•
오버플로우 위험 존재
2.2. 곰셉, 나눗셈 활용
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;
C++
복사
•
세 번의 산술 연산만 필요 → 시간 복잡도:
•
오버플로우 위험 존재
•
0 나누기 위험 존재
2.3. XOR 비트 연산 활용
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;
C++
복사
•
같은 데이터로 xor 연산 두 번하면 원래 데이터로 돌아오는 성질 이용
•
세 번의 비트 연산만 필요 → 시간 복잡도: