LeetCode 190 - Reverse Bits

32비트 부호 없는 정수의 이진 비트 순서를 거꾸로 뒤집어 새로운 정수 값을 계산하는 Easy 문제다. 문자열로 변환하지 않고 비트 연산자(&, <<, >>)만 활용하여 32회 순회로 제자리에서 비트를 조립했다.

문제 링크 & 설명

문제 링크: 190. Reverse Bits
요약: 주어진 32비트 부호 없는 정수 n의 모든 이진 비트를 역순으로 배치한 뒤, 그 결과를 정수 형태로 반환한다.

예를 들어 최하위 비트(LSB)에 있던 값은 결과 정수의 최상위 비트(MSB) 위치로 이동해야 한다. 숫자를 2진수 문자열로 바꾸어 뒤집는 방법도 가능하지만, 비트 단위 연산을 사용하면 추가 메모리 할당 없이 고정된 연산만으로 깔끔하게 처리할 수 있다.

접근 방법

결과를 담을 res를 0으로 초기화한 뒤, 32비트 전체를 32번의 루프로 한 비트씩 처리한다.

res = 0
for _ in range(32):
    bit = n & 1
    res = (res << 1) | bit
    n >>= 1

최하위 비트 추출: n & 1 연산으로 현재 n의 가장 오른쪽 1비트를 추출한다.
결과 누적: 기존의 res를 왼쪽으로 1칸 시프트(res << 1)하여 새로운 비트가 들어갈 자리를 만들고, OR 연산(| bit)으로 추출한 비트를 채운다.
입력 시프트: 처리가 끝난 n을 오른쪽으로 1칸 시프트(n >>= 1)하여 다음 비트를 준비한다.

이 과정을 32번 반복하면 n의 첫 번째 비트(원래 LSB)가 31번 왼쪽으로 밀려 결과적으로 MSB 자리까지 도달하게 된다.

복잡도 분석

시간 복잡도: O(1)
- 정수의 비트 수가 32개로 고정되어 있으므로 루프는 항상 정확히 32번 실행된다.
공간 복잡도: O(1)
- 추가적인 자료구조나 문자열 생성 없이 몇 개의 정수 변수만 사용한다.

구현 코드

class Solution:
    def reverseBits(self, n: int) -> int:
        res = 0
        for _ in range(32):
            bit = n & 1
            res = (res << 1) | bit
            n >>= 1
        return res

요약 및 회고

문자열 변환이나 복잡한 배열 조작 대신 비트 시프트와 마스킹을 활용하면 정수 연산의 본질에 가장 가깝게 문제를 해결할 수 있다. 비트 이동 순서를 ‘결과값 시프트 후 비트 삽입’으로 일관되게 유지하면 32회 루프 종료 시점에 자연스럽게 정확한 32비트 정렬이 완성된다.