C++에서 숫자의 모든 비트를 반전시키는 효율적인 프로그램 작성 방법

이 문제에서는 부호 없는 정수(unsigned int) n이 주어지며, 우리의 목표는 이 숫자의 모든 비트를 거꾸로 뒤집었을 때 얻어지는 새로운 수를 반환하는 프로그램을 작성하는 것입니다.

먼저 예시를 통해 문제를 이해해 보겠습니다.

입력

n = 1

출력

2147483648

설명

1의 이진수 표현은 000...0001이며, 이를 뒤집으면 100...0000이 됩니다.

방법 1: 비트 위치 계산식 활용

가장 직관적인 해결 방법은 간단한 공식을 사용하는 것입니다. 숫자의 이진수 비트를 처음부터 끝까지 순회하면서 값이 1로 설정된 비트(set bit)의 위치 i를 찾습니다. 그런 다음 해당 비트를 반대편 위치로 옮기기 위해 다음 공식을 적용합니다.

((총 비트 수) - 1) - i

즉, 하위 비트에 있던 1은 상위 비트로, 상위 비트에 있던 1은 하위 비트로 이동하게 됩니다.

구현 예제

#include<iostream>
using namespace std;
unsigned int reverseBitNumber(unsigned int num) {
    unsigned int totalNumberOfBits = sizeof(num) * 8;
    unsigned int reverseNumber = 0, temp;
    for (int i = 0; i < totalNumberOfBits; i++){
        if((num & (1 << i)))
            reverseNumber |= (1 << ((totalNumberOfBits - 1) - i));
    }
    return reverseNumber;
}
int main() {
    unsigned int n = 21;
    cout<<"The number is "<<n<<endl;
    cout<<"The number which has reverse bits of the number is :"<<reverseBitNumber(n);
    return 0;
}

출력

The number is 21
The number which has reverse bits of the number is :2818572288

방법 2: 비트 시프트 연산 활용

두 번째 방법은 시프트(shift) 연산을 이용하는 것입니다. 입력값의 비트를 오른쪽으로 한 칸씩 시프트하면서 값이 0이 될 때까지 반복하고, 매 단계마다 추출된 최하위 비트를 결과 변수에 왼쪽으로 시프트하며 차례대로 채워 넣습니다. 마지막으로 남은 시프트 횟수만큼 결과를 왼쪽으로 밀어주면 전체 32비트 기준으로 완전히 뒤집힌 값을 얻을 수 있습니다.

구현 예제

#include<iostream>
using namespace std;
unsigned int reverseBitNumber(unsigned int n){
    unsigned int rem_shift = sizeof(n) * 8 - 1;
    unsigned int reverseNubmer = n;
    n >>= 1;
    while(n){
        reverseNubmer <<= 1;
        reverseNubmer |= n & 1;
        n >>= 1;
        rem_shift--;
    }
    reverseNubmer <<= rem_shift;
    return reverseNubmer;
}
int main(){
    unsigned int n = 21;
    cout<<"The number is "<<n<<endl;
    cout<<"The number which has reverse bits of the number is :"<<reverseBitNumber(n);
    return 0;
}

출력

The number is 21
The number which has reverse bits of the number is :2818572288

마무리

두 방법 모두 32비트 부호 없는 정수를 기준으로 동작하며, 시간 복잡도는 O(비트 수), 즉 O(32)로 상수 시간에 가깝게 처리됩니다. 첫 번째 방법은 로직이 명확하여 이해하기 쉽고, 두 번째 방법은 불필요한 연산을 줄여 실제 실행 속도 면에서 더 유리한 경우가 많습니다. 비트 조작 문제를 학습할 때 두 접근 방식을 모두 익혀두면 도움이 됩니다.