'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List


class Solution:
    # O(1) for S and T
    def reverseBits(self, n: int) -> int:
        res, power = 0, 31
        while n:
            res += (n & 1) << power
            # print ("{0:b}".format(res))
            n = n >> 1
            power -= 1
        return res
    
    # divide and conquer, no loop
    def reverseBits1(self, n):
        n = (n >> 16) | (n << 16) # half and switch
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8)
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4)
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2) # c: 1100
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1) # a: 1010
        return n