[Programmers] Lv2 다음 큰 숫자 Java

문제 출처

[프로그래머스 코딩 테스트 연습]

https://school.programmers.co.kr/learn/courses/30/lessons/12911

프로그래머스

 

문제 풀이

이 문제는 다음과 형태로 진행이 된다.

예시는 1001110을 예시를 든다.

1. 가장 오른쪽에 있는 1을 구하기
   ex) 1001110 → 0000010
2. 1번 왼쪽에서 가까운 0비트에 1비트로 바꾸고 나머지 자르기
   ex) 1001110 → 1010000
3. 비트수 맞추기
   ex) 1010000 → 1010011

위 단계를 그림으로 나타낸 것

 

1. 가장 오른쪽에 있는 1을 구하기

1001110에서 가장 오른쪽 비트를 가져오는 방법이 무엇일까?

일단 and 연산에 대해 알아보자.

and 연산은 서로 같으면 1 다르면 0이 되는 비트연산이다.

and 연산을 사용한다면 가장 오른쪽에 있는 1을 구하려면 가장 오른쪽 1을 제외하고 전부 달라야 된다.

즉 0110010이 되어야 한다.

0110001에서 +1을 하면 된다.

여기서 더 나아가면 0110001은 원래 비트의 1의 보수이다.

그리고 2의 보수는 1의 보수에서 +1을 하면 되고 이는 컴퓨터에서 음수를 표현하는 방법 중하나이다.

즉 Java에서도 -int를 하면 2의 보수로 저장이 된다.

 

정리하면 다음과 같다.

1001110의 1의 보수를 구하면 0110001이 된다.

여기서 1을 더하면 0110010이 된다. - - - - - (1)

(1) 번 비트와 원래 비트를 and 연산하면 가장 오른쪽에 있는 1비트를 구할 수 있다.

그리고 (1) 번 비트는 컴퓨터와 java에서 음수를 표현하는 방법이다.

and 연산이란 각 비트를 비교했을때 같으면 1, 다르면 0이 되는 연산이다.

 

    1001110
and 0110010
    0000010

 

이와 같이 0000010 가장 오른쪽에 있는 비트를 얻어 낼 수 있다.

n & -n

 

2. 1번 왼쪽에서 가꾸운 0비트에 1비트로 바꾸고 나머지 자르기

 

그림에서는 바꾸기 다음에 자르기로 했지만 사실상 1번에서 얻은 비트를 원래 비트랑 더하면 된다.

더하면 자릿수가 바뀌게 되면서 나머지가 잘라지게 된다.

 

자릿수 바뀌면서 자동으로 바꾸기와 나머지 자르기가 되는 계산 과정

 

n = n + (n & -n);

 

3. 비트수 맞추기

 

비트 수를 맞추려면 추가해야 하는 비트를 추가해 주면 된다.

추가해야 할 비트 수를 알려면 자르기 전후의 비트 수의 차를 구하면 된다.

자바에서 비트의 수를 얻으려면 Integer.bitCount(int)을 사용하면 된다.

int bitCount = Integer.bitCount(n);
n = n + (n & -n);
int bitCount2 = Integer.bitCount(n);

 

오른쪽에서부터 n개의 비트를 추가하는 방법을 알아보자.

 

0000001을 10진수로 변환하면 1이다

0000011을 10진수로 변환하면 3이다

0000111을 10진수로 변환하면 7이다

0001111을 10진수로 변환하면 15이다

 

1, 3, 7, 15는 (2^ n) - 1식으로 올라가고 있다. (n은 비트수)

즉 n에 비트의 차를 넣고 2번에서 얻은 n에 더하면 된다.

n += Math.pow(2, bitCount - bitCount2) - 1;

 

소스 코드

public class Solution {
    
    public int solution(int n) {
        int bitCount = Integer.bitCount(n);
        n = n + (n & -n);
        int bitCount2 = Integer.bitCount(n);
        n += Math.pow(2, bitCount - bitCount2) - 1;
        return n;
    }
 
}