2021-01-21Algorithm4 minutes read (About 566 words) 0 visits

[자바JAVA]190. Reverse Bits

문제 190. Reverse Bits

주어진 32비트 unsigned integer를 역순으로 만들어 리턴하는 문제이다.
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.

입출력예시

//예시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.

//예시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.

제약조건 : 길이32의 이진수만 입력값으로 가능하다. The input must be a binary string of length 32

unsigned integer란?

자바에는 unsigned integer가 없다. 생소하기때문에 개념을 찾아보았다.
unsigned와 signed integer가 있다. 여기서 sign은 부호를 뜻한다.
int의 범위는 –2,147,483,648 ~ 2,147,483,647이다.
unsigned integer는 음수를 가질 수 없다. 양수인 부분 즉, 0 ~ 2,147,483,647만을 unsigned integer라고 한다.
단어가 생소해서 그렇지 그리 어려운 개념은 아니다.

int and unsigned int are two distinct integer types. (int can also be referred to as signed int, or just signed; unsigned int can also be referred to as unsigned.)
As the names imply, int is a signed integer type, and unsigned int is an unsigned integer type. That means that int is able to represent negative values, and unsigned int can represent only non-negative values.
출처 : https://stackoverflow.com/questions/5739888/what-is-the-difference-between-signed-and-unsigned-int

비트 AND 와 SHIFT 연산자

예를들어 00110이 있다면 11001을, 11100이면 00111을 리턴해줘야한다.
비트가 나왔으니 비트연산자를 떠올려보자.

비트 AND 연산자 : 비트연산자 &를 사용하면 같은 값이면 해당 값을 반환하고 다른 값이면 0을 반환환다.

비트 SHIFT 연산자 : <<n n만큼 왼쪽으로 이동한다. 이동하고 빈곳에는 0을 넣는다.

위 둘을 이용해 한 비트씩 계산할 수 있다.

비트 OR 연산자 : 두 비트가 모두 0일때만 0을 반환한다.

제일 오른쪽의 비트부터 AND연산시 0보다 숫자가 클 경우 OR연산자를 이용해 역으로 출력해준다.

코드

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int ans = 0;
		// 32비트 제약
        for(int i=0; i<32; i++){
            ans = ans <<1;
            if((n & 1) >0){
                ans = ans | 1;
            }
            n = n >>1;
        }
        return ans;
    }
}