C++에서 양끝 비트 교환으로 부호 없는 정수 최대화하기

문제 설명

주어진 부호 없는 정수를 극단 위치(양쪽 끝)의 비트를 서로 교환하여 최댓값으로 만드는 것이 이번 문제입니다. 즉, 첫 번째 비트와 마지막 비트, 두 번째 비트와 뒤에서 두 번째 비트를 차례로 짝지어 교환해 나갑니다.

예를 들어 입력 값이 8이라면 이진 표현은 다음과 같습니다.

00000000 00000000 00000000 00001000

극단 위치의 비트들을 모두 교환하면 아래와 같이 바뀌며, 그 십진수 값은 268435456이 됩니다.

00010000 00000000 00000000 00000000

알고리즘

1. 원래 수의 복사본을 만들어 기준으로 사용합니다.
2. 낮은 자리(하위) 비트가 1이고 높은 자리(상위) 비트가 0인 경우에만 두 비트를 실제로 교환합니다. 하위 비트의 위치가 상위 비트의 위치보다 작아질 때까지 이 과정을 반복합니다.
3. 교환이 완료된 새로운 수를 반환합니다.

여기서 핵심은 두 비트가 서로 다를 때만 교환이 의미 있다는 점입니다. 두 비트가 같으면(0과 0 또는 1과 1) 교환해도 값이 변하지 않기 때문입니다. 두 비트가 다르고 더 큰 값을 만들려면 반드시 상위 비트를 1로, 하위 비트를 0으로 만들어야 합니다.

구현 예제

#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
ull getMaxNumber(ull num){
    ull origNum = num;
    int bitCnt = sizeof(ull) * 8 - 1;
    int cnt = 0;
    for(cnt = 0; cnt < bitCnt; ++cnt, --bitCnt) {
        int m = (origNum >> cnt) & 1;
        int n = (origNum >> bitCnt) & 1;
        if (m > n) {
            int x = (1 << cnt | 1 << bitCnt);
            num = num ^ x;
        }
    }
    return num;
}
int main(){
    ull num = 8;
    cout << "Maximum number = " << getMaxNumber(num) << endl;
    return 0;
}

동작 원리

코드에서는 두 개의 포인터(cnt와 bitCnt)를 사용해 가장 낮은 자리와 가장 높은 자리부터 중앙을 향해 동시에 이동합니다. 각 단계에서 시프트 연산과 AND 연산(>> cnt & 1)으로 해당 위치의 비트 값을 읽어옵니다.

하위 비트가 1이고 상위 비트가 0이라면, 두 위치에 해당하는 마스크((1 << cnt) | (1 << bitCnt))를 만든 뒤 XOR 연산으로 두 비트를 한 번에 뒤집습니다. XOR은 같은 비트를 두 번 적용하면 원래 값으로 돌아오는 성질이 있어, 필요한 두 자리만 정확히 교환할 수 있습니다.

출력 결과

위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.

Maximum number = 268435456