[프로그래머스] Level 2 다음 큰 숫자

문제 링크

programmers.co.kr/learn/courses/30/lessons/12911

풀이

n+1부터 시작해서 1씩 증가시키며 켜진 비트의 수가 같은 경우를 찾으면 된다.

이렇게 풀 경우 최악의 경우는 어떻게 될까?
대강 따져보자면 n은 최대 100만이므로 사용되는 비트의 수는 많아봤자 20개다.
20개의 비트를 재조정하는 것으로 항상 모든 답이 나올 수 있으니 연산의 수는 $2^{20}$을 넘지 않는다.

C++ 코드

프로그래머스는 clang++으로 컴파일한다.
gcc나 clang에는 켜진 비트의 수를 구하는 내장함수인 __builtin_popcount라는 함수가 있다.

int solution(int n) {
    int cnt = __builtin_popcount(n);
    for (int i = n + 1; ; ++i)
        if (__builtin_popcount(i) == cnt) return i;
}

Java 코드

켜진 비트의 수를 구할 때 Integer의 bitCount 메서드를 사용하자.

class Solution {
    public int solution(int n) {
        int cnt = Integer.bitCount(n);
        for (int i = n + 1; true; ++i)
            if (Integer.bitCount(i) == cnt) return i;
    }
}