[Leetcode/Python] Reverse Bits

Top Interview Questions 의 Easy Collection에 있는 문제입니다.         
문제는 여기서 볼 수 있습니다.

Reverse bits of a given 32 bits unsigned integer.

Note:

• Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
• In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.

 

Example 1:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

 

Constraints:

• The input must be a binary string of length 32

 

Follow up: If this function is called many times, how would you optimize it?

 

풀이

 

- 비트 전체를 순회하면서 1 과 AND 연산을 반복합니다.

- n 의 가장 오른쪽에 있는 값이 answer 의 가장 왼쪽에 가야 하므로 answer 는 0 부터 왼쪽 쉬프트, n 은 오른쪽 쉬프트를 반복하며 계속 비교하면 됩니다.

 

Code:

class Solution:
    def reverseBits(self, n: int) -> int:
        answer = 0
        # Constraints: The input must be a binary string of length 32
        for i in range(32):
            answer = (answer << 1) + (n & 1)
            n >>= 1
        return answer