C++에서 부호 없는 32비트 정수의 비트 반전 구현하기

문제 개요

부호 없는 32비트 정수 x가 하나 주어졌다고 가정해 봅시다. 이 숫자의 이진 표현에서 모든 비트의 순서를 거꾸로 뒤집는 것이 우리의 과제입니다. 예를 들어 이진 표현이 00000000000000000000001001110100이라면, 비트를 반전한 결과는 00101110010000000000000000000000이 됩니다. 마지막에는 비트를 뒤집은 후의 실제 숫자 값을 반환해야 합니다.

알고리즘 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• 주어진 수를 n이라고 합니다.
• 결과를 저장할 변수 answer를 0으로 초기화합니다.
• i를 31부터 0까지 1씩 감소시키며 반복합니다.
  • answer에 (n AND 1)을 OR 연산한 후 왼쪽으로 i비트 시프트한 값을 누적합니다.
  • n을 오른쪽으로 1비트 시프트합니다.
• answer를 반환합니다.

구현 예제

아래의 C++ 구현 예제를 살펴보면 이해에 도움이 됩니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t ans = 0;
        for(int i = 31; i >= 0; i--){
            ans |= (n & 1) << i;
            n >>= 1;
        }
        return ans;
    }
};
main(){
    Solution ob;
    cout << ob.reverseBits(0b00000000000000000000001001110100);
}

입력

0b00000000000000000000001001110100

출력

775946240

동작 원리

이 알고리즘은 입력 값의 최하위 비트(LSB)부터 하나씩 추출하여, 결과 변수의 최상위 비트(MSB) 위치부터 차례대로 채워 넣는 방식으로 동작합니다. 루프가 한 번 실행될 때마다 n은 오른쪽으로 1비트씩 이동하고, 추출된 비트는 answer의 대응되는 위치에 배치됩니다. 총 32번의 반복이 끝나면 원래 수의 비트 순서가 완전히 뒤집힌 결과를 얻게 됩니다.

이 방법의 시간 복잡도는 고정된 32회 반복만 수행하므로 사실상 O(1)이며, 별도의 추가 메모리 없이 비트 연산만으로 문제를 해결할 수 있다는 장점이 있습니다. 임베디드 시스템이나 네트워크 프로토콜 처리처럼 비트 단위 조작이 필요한 분야에서 자주 활용되는 기법입니다.