리트코드 - 190. Reverse Bits

리트코드 - 190. Reverse Bits

출처 - https://leetcode.com/problems/reverse-bits/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

32비트로 표현된 양의 정수 값을 거꾸로 뒤집는 문제입니다.

주의사항:

1. 어떤 언어들은 Java와 같이 부호 없는 정수(unsigned integer) 형식을 지원하지 않습니다. 이 경우에는 입력과 출력 모두 부호 있는 정수(signed integer) 형식으로 제공됩니다. 이것은 구현에 영향을 미치지 않는데, 부호 있는 정수와 부호 없는 정수는 내부 이진 표현에서 동일하기 때문입니다. 다시 말해, 정수의 이진 표현은 그것이 부호 있는 정수인지 부호 없는 정수인지와 상관없이 동일합니다.
2. 자바와 같은 언어에서, 컴파일러는 2의 보수 표기법(2's complement notation)을 사용하여 부호 있는 정수(signed integer)를 표현합니다. 예제 2에서의 입력은 -3이라는 부호 있는 정수를 나타내며 출력은 -1073741825라는 부호 있는 정수를 나타냅니다.

 

의사코드

int result = 0 반복문 시작 (32번 반복)     result = result를 오른쪽으로 밈 OR n & 1     n = n >> 1 반복문 종료 result 리턴

 

풀이코드

public class Solution {
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);
            n = n >> 1;
        }
        return result;
    }
}

코드설명

비트 연산자를 이용한 풀이이다.

비트 연산에서 |(or)은 둘 중 하나만 1이면 0이 되는 연산이다.

result를 왼쪽으로 밀면 그자리는 0이 되고, n & 1 연산을 통해 마지막 자리를 확인해서 1 또는 0을 확인한다.

 

n이 1이라면 마지막 자리는 1이 될 것이고, 0이면 마지막 자리는 0이 될 것이다.

그리고 n을 왼쪽으로 밀어 없애고 다시 반복하면 된다.

 

시간복잡도 - O(1)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

모두를 위한 컴퓨터 과학 강의를 보며 배웠던 내용인데 까먹어서 다시 봤다.

비전공이다보니 전공에서 왜 C를 먼저 배우는지 알게되는 문제인 것 같다.

 

봤던 내용이지만 다시 공부하며 정리를 해야겠다.

 

정리

자바에서 비트연잔자 사용방법