[LeetCode] - 190. Reverse Bits

   LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Reverse Bits" 문제입니다.

--> https://leetcode.com/problems/reverse-bits/description/ 

 

문제 : 

Reverse bits of a given 32 bits unsigned integer.

Note : 

   - Note that in some languages, such as Java, there is no unsigned interger type. In this case, both input and output will be given as a signed interger 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 intergers 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.

---

한국어로 간단히 설명하자면, 이 문제는 32비트 부호 없는 정수의 비트를 반대로 뒤집는 함수를 작성하라고 요구하며, 입력과 출력은 32비트 정수로 주어지고, 자바와 같은 언어에서는 부호 있는 정수로 취급됩니다.

 

저는 우선 자바로 이 문제를 접근했으며, 풀이를 보여드리겠습니다 :

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            // Extract the least significant bit of n
            int bit = n & 1;
            // Shift this bit to its reversed position and combine with res
            res = (res << 1) | bit; // We can also do (res * 2) instead of (res << 1)
            // Shift n to the right to process the next bit
            n >>= 1;
        }
        return res;
    }
}

 

위와 같이, 우선 int가 32비트라는 것을 인지하고, 32 만큼 for loop을 돌리고, 그 안에서는 매번 n의 최하위 비트를 추출해 오며,  이 비트를 반전된 위치로 이동시키고 res와 결합합니다. 그리고나서, 다음 비트를 처리하기 위해 n을 오른쪽으로 이동시킵니다. 그러다 보면 res라는 정수 변수에는 n의 반전된 이진 표현의 값이 저장되어 리턴합니다.

 

Runtime of my code