[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의 반전된 이진 표현의 값이 저장되어 리턴합니다.
