Reverse Bits

문제 링크

• https://leetcode.com/problems/reverse-bits/

문제 설명

32비트의 양의 정수 n이 주어졌을 때, 이 정수의 비트를 반대로 뒤집어 반환하는 함수를 작성하세요.

• 입력: 정수 n (32비트)
• 출력: 비트를 뒤집은 결과 정수

예제

• 예제 1
  • 입력: n = 00000010100101000001111010011100
  • 출력: 964176192 (00111001011110000010100101000000)
  • 설명: 입력된 이진수는 43261596을 나타내고, 이 비트를 뒤집으면 00111001011110000010100101000000이 되어 964176192를 반환합니다.
• 예제 2
  • 입력: n = 11111111111111111111111111111101
  • 출력: 3221225471 (10111111111111111111111111111111)
  • 설명: 입력된 이진수는 4294967293을 나타내고, 이 비트를 뒤집으면 10111111111111111111111111111111이 되어 3221225471을 반환합니다.

풀이 전략

비트를 뒤집는 문제이므로 주어진 정수의 이진 표현을 한 비트씩 확인하며 뒤에서부터 결과에 추가하는 방식으로 해결할 수 있습니다.

1. Bit Manipulation:
   • 매 루프마다 n의 마지막 비트를 확인하여 결과에 추가하고, n을 오른쪽으로 쉬프트하여 다음 비트를 확인합니다.
   • 결과를 왼쪽으로 한 비트씩 쉬프트하여 새로운 비트를 추가하고, n의 마지막 비트를 결과에 추가합니다.
   • 총 32번 반복하며 결과에 모든 비트를 채웁니다.
2. 비트 쉬프트 및 OR 연산 사용:
   • 각 단계에서 결과 변수 result를 왼쪽으로 한 비트씩 쉬프트한 후, n의 마지막 비트를 OR 연산으로 추가합니다.
   • n은 오른쪽으로 쉬프트하여 모든 비트를 차례로 확인합니다.
   • 반복이 끝나면 뒤집힌 비트 순서로 저장된 result를 반환합니다.

코드 분석

class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        for _ in range(32):  # 32비트 반복
            result = (result << 1) | (n & 1)  # result를 왼쪽으로 쉬프트하고 n의 마지막 비트를 추가
            n >>= 1  # n을 오른쪽으로 쉬프트하여 다음 비트를 확인
        return result

• 코드 설명:
  • result를 0으로 초기화하여 결과를 저장할 공간을 만듭니다.
  • 32번 반복하며 각 단계에서 다음 작업을 수행합니다:
    • result를 왼쪽으로 한 비트 쉬프트하여 비트를 추가할 자리를 마련합니다.
    • n & 1을 사용하여 n의 마지막 비트를 가져와 result의 마지막 비트로 추가합니다.
    • n을 오른쪽으로 한 비트 쉬프트하여 다음 비트를 준비합니다.
  • 반복이 끝나면 result는 n의 뒤집힌 비트 순서로 채워지며, 이를 반환합니다.
• 시간 복잡도: (O(1)), 비트 수가 고정(32비트)이므로 상수 시간에 수행됩니다.
• 공간 복잡도: (O(1)), 추가적인 저장 공간을 거의 사용하지 않습니다.

요약

• 이 문제는 비트 조작과 비트 쉬프트 연산을 사용하여 효율적으로 해결할 수 있습니다.
• 각 비트를 하나씩 결과에 추가하는 방식으로, n의 비트를 뒤집어서 result에 저장합니다.
• 시간 및 공간 복잡도 모두 (O(1))로 매우 효율적인 풀이입니다.