연습문제 > 다음 큰 숫자

문제 위치 : https://school.programmers.co.kr/learn/courses/30/lessons/12911

프로그래머스

 

builtin_popcount라는 함수를 사용하여 풀었다.

이는 이진수 변환시의 1의 갯수를 새어주는 함수이다.

using namespace std;

int solution(int n) {
    int c = n;
    int count = 0;
    
    while (c) {
        c &= (c - 1);  
        count++;
    }

    int p = n;
    while (true) {
        p++;
        if (__builtin_popcount(p) == count) {
            return p;
        }
    }
}

 

다른 함수를 사용한 유사한 풀이는 다음과 같다.

 

#include <bitset>

using namespace std;

int solution(int n) {
    int num = bitset<20>(n).count();

    while (bitset<20>(++n).count() != num);
    return n;
}

 

근데 위와 같이 이를 사용하는 것 외에 비트 연사자를 사용하는 풀이가 있었다.

 

int solution(int n) {
    int pivot = n & -n;
    int before = ((n ^ (n + pivot)) / pivot) >> 2;
    return (n + pivot) | before;
}

 

정말 간단하고 명료하다.

 

한줄 씩 설명하자면

int pivot = n & -n;

 

부분이다. -n은 n의 2의 보수이다.

그리고 이를 & 연산하게 되면 가장 오른쪽에 있는 1의 위치를 얻을 수 있게 된다.

이는 보수의 성질을 이용한 것이다. 이 부분이 너무 깔끔했다.

 

나 또한 가장 작은 1의 위치를 구하는 방식을 생각했지만 나는 문자열로 변환하여 풀 생각을 하다 실패하였기 때문이다.

 

그 다음은 before를 구하는거다.

int before = ((n ^ (n + pivot)) / pivot) >> 2;

 

먼저 pivot+n이다.

 

이는 이진 표현에서 pivot위치에 1을 더해준 것과 같은 연산이다.

 

바로 다음 큰 수인데 왜 1이 있는 위치에 1을 더하냐고 생각할 수도 있는데 이는 0이 있는 위치에 연산하는 단계가 무의미하기 때문이다. 

 

문제 조건으로는 이진 표현하였을 때 1의 갯수가 같다 라는 조건이 붙어있다.

 

그 말인 즉슨 0의 위치에 1을 더해도 1의 갯수가 변경되므로 해당 값은 절대 정답이 될 수 없다.

 

그렇기 때문에 다음 큰 값은 최소한 pivot의 위치에 1을 더한 것보다는 항상 크다는 뜻이며 우리가 이를 기준으로 삼을 수 있는 이유이다.

 

그 다음으로는 n ^ (n + pivot)이다.

 

이는 둘의 XOR의 결과이다.

 

n = 78 (1001110), n + pivot = 80 (1010000)일 때, XOR 연산 결과는

n = 78    ->  1001110
n + pivot = 80  ->  1010000
--------------------------------
n ^ (n + pivot)  ->  0011110

 

다음과 같이 이루어진다.

 

즉, 변경된 비트들의 위치가 0011110으로 나타나는 것이다.

 

그리고 문제에서는 이를 계산하는데 있어 가장 작은 다음 큰수를 고르는 것이다.

 

before는 나중에 n+pivot의 1의 갯수를 보정해주는데 사용되므로 pivot을 통한 상대 위치를 골라줘야 한다.

 

따라서

 

/ pivot 연산이 들어간다.

 

(n ^ (n + pivot)) / pivot 의 계산 결과는 

0011110 / 0000010 = 0001111

•  

같은 식으로 1들의 위치가 가장 작은 0이 되도록 맞춰주는 것이다.

 

그 다음 >>2 연산을 해준다.

 

이는 before가 조정해주는 비트의 위치들이 n + pivot과 n사이에 존재해야기 때문에 조정해주는 것이다. 

 

마지막 

return (n + pivot) | before;

 

연산은 before가 가지고 있는 비트 정보를 바탕으로 n+pivot에 부족한 1의 갯수를 보정해주는 것이다.