[LeetCode] 190. Reverse Bits

문제

leetcode.com/problems/reverse-bits/

Reverse Bits - LeetCode

 

잠깐만

"If this function is called many times, how would you optimize it?"

문제는 풀어도 최적화가 관건이네요~

 

코드

21년 4월 7일 코드

class Solution {
    func reverseBits(_ n: Int) -> Int {
        var calN = n
        var result = 0
        
        var shiftNum = 31
        while shiftNum > -1 {
            if calN == 0 {
                break
            }
            
            result += (calN & 1) << shiftNum
            shiftNum -= 1
            calN >>= 1
        }
        return result
    }
}

 

22년 2월 16일 코드

class Solution {
    func reverseBits(_ n: Int) -> Int {
        var inputNum = n
        var result = 0
        for _ in 1...32 {
            result = result << 1
            result |= inputNum & 1
            inputNum = inputNum >> 1
        }
        return result
    }
}

설명

다음 문제를 풀어보셨으면 어느정도 문제 접근(비트 및 시프트 연산) 감이 있을거에요

leetcode.com/problems/number-of-1-bits/

Number of 1 Bits - LeetCode

num의 비트 연산을 통해 마지막 자리의 수를 알아내고, 시프트 한 이후 값을 더했습니다.

회고

처음엔 다음과 같이 구현했습니다. 단순 시프트 계산을 통해, reverse를 구했죠

 

하지만, calN의 값이 0이 된 순간 값을 더할필욘 없고, 시프트 연산만 필요하다는 것을 깨달았고, 로직을 구현했습니다.

메모리에서 많은 상승이 있었네요.

 

더욱 더 최적화를 위해, while문으로 변경해봤고, 로직 자체를 변경 했습니다.

calN이 0이 된 순간 이후에도 시프트 연산을 수행할 필욘 없어졌죠. 

 

22년 2월 16일에 작성한 코드 결과입니다.

참고로 런타임과 메모리 사용량은 LeetCode 상황에 따라 변동이 존재합니다.