Python concise 2 solutions


  • 0

    If this calculation happens only once, we can just check digit one by one from right to left.
    If we use this function multiple times, we can create a lookup table (hash map) to store the reversed data as a cache, by 1 bit.

    without map:

    class Solution:
        # @param n, an integer
        # @return an integer
        def reverseBits(self, n):
            res = 0
            i = 32
            while True:
                lastBit = n & 1
                res += lastBit
                
                i -= 1
                if i <= 0:
                    break
                res, n = res << 1, n >> 1
            return res
    

    with lookup table

    cache = {}
    
    class Solution:   
        def reverseBits(self, n):
            res = 0
            i = 0
            while True:
                shifted = n >> 8 * i
                b = shifted & 255 # extract last 8 bytes data by calculating & 11111111
                
                if b in cache:
                    rb = cache[b]
                else:
                    rb = self.reverseBit(b)
                    cache[b] = rb
                res += rb
                i += 1
                if i >= 4:
                    break
                res = res << 8
            return res
    
        def reverseBit(self, n):
            res = 0
            i = 8
            while True:
                lastBit = n & 1
                res += lastBit
                
                i -= 1
                if i <= 0:
                    break
                res, n = res << 1, n >> 1
            return res     
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.