LeetCode 190(Reverse Bits, Python)

1. 문제 링크

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

Reverse Bits - LeetCode

2. 문제 설명

• 주어진 정수를 2진법으로 나타낸 후 이를 앞뒤 역순으로 뒤집은 수를 10진법으로 변환하여 반환
• 단, 2진법은 32비트로 즉, 32자리 2진법으로 나타내며 자릿수가 부족하면 앞쪽에 0으로 채움
• 예시)
  • n=1이 입력되면 32자리 2진법 (00000000000000000000000000000001)로 나타냄.
  • 이를 역순으로 바꾼 후 (10000000000000000000000000000000) 다시 10진법으로 바꾸어 2^32를 반환

3. 처음 풀이

• 단순히 주어진 10진법 숫자를 → 2진법으로 변환 후 → 32자리로 앞에 '0'을 padding한 뒤에,
• 다시 2진법을 10진법으로 변환한 값을 반환

class Solution:
    def reverseBits(self, n: int) -> int:

        result = ''
        
        if n == 0: # n=0이면 뒤집어도 0이므로 0 반환
            return 0 

        else: # 10진법을 2진법으로 변환: 2로 나눈 나머지를 계속 concat 
            while n > 1:
                result = str(n % 2) + result
                n = n // 2
            result = '1' + result

        while len(result) != 32: # 32자리가 될때까지 앞에 '0'을 padding 
            result = '0' + result 

        output = 0
        for index, i in enumerate(result): # 다시 2진법을 10진법으로 변환
            output += int(i) * 2 ** index
        
        return output

 

4. 다른 풀이

• 비트연산자 >>
  • a>>b는 a의 비트를 오른쪽으로 b만큼 이동시킴
• 비트연산자 |
  • OR 연산
• 32번 for문을 돌며 n을 32bit로 나타내었을 때 오른쪽부터 하나씩 check
• n>>i 연산을 통해 n(32bit)를 우측으로 i칸 밀어서 현재 확인중인 비트를 가장 우측으로 옮기고,
• &1 연산을 하여 확인 중인 비트 (0 or 1)를 그대로 가져옴
• bit<<(32-i) 연산을 하여 확인 중인 비트를 역순 위치에 넣음
• res와 bit를 |연산하여 결과 업데이트

class Solution:
    def reverseBits(self, n: int) -> int: #예시 n=10(0000 0000 0000 0000 0000 0000 0000 1010)
        res=0
        for i in range(32): #예시 i=0
            bit=(n>>i)&1 #n>>0은 오른쪽으로 0칸 밀어서 0000 0000 0000 0000 0000 0000 0000 1010, &1(가장 우측만1) 연산하면 가장 우측이 1이면 1, 아니면 0이므로 현재 bit=0
            res=res|(bit<<(31-i)) #bit<<31하면 왼쪽 31칸 밀어서 0000 0000 0000 0000 0000 0000 0000 0000, res=0과 |연산하면 모두 0이므로 res=0
						#i=1일 때
						#n>>1은 오른쪽으로 1칸 밀어서 0000 0000 0000 0000 0000 0000 0000 0101, &1 연산하면 bit=1
						#bit<<30하면 왼쪽 30칸 밀어서 0100 0000 0000 0000 0000 0000 0000 0000, |0 연산하면 res=0100 0000 0000 0000 0000 0000 0000 0000
						#n의 가장 우측 10이 res의 가장 좌측 01로 반영됨
						#i=2일 때는 n의 우측 3번째 0이 res의 좌측 3번째 0으로 반영, i=3일 때는 n의 우측 4번째 1이 res의 좌측 4번째 1로 반영... 반복
						
        return res

• 다른 풀이2 
  
  • 기존에는 2진법으로 변환 시 직접 계산을 했는데, bin함수를 쓰면 쉽게 2진법으로 변환 가능
    • bin으로 반환하면 '0b'(진법표기)가 붙어서 이를 생략하여 저장한 다음,
    • 역순으로 뒤집고 32 자리 'padding' 후 다시 10진법으로 변환
      • 10진법 변환 시 int(string,n)을 통해 빠르게 변환 가능

class Solution:
    def reverseBits(self, n: int) -> int:
        b = bin(n)[2:] #2진법으로 변환 후 진법 표기 0b를 생략하여 저장
        l = len(b) #길이를 확인 후
        b = b[::-1] #역순으로 뒤집고
        b = b + ''.join(['0' for _ in range(32 - l)]) #길이 32에서 모자란 만큼 앞에 0을 채움
        return int(b, 2) #10진법으로 변환

 

5. 배운 점

• 비트연산자
• bin 함수, int(string,n) 함수