다음 큰 숫자

• 그리디하게 생각하자. 2진수 표현을 기준으로 최하위비트부터 스캔하면서, 현재 비트는 1이고 상위 비트는 0이 되는 위치를 찾는다. 그렇게 찾아낸 것이 하위 n번째 비트였다고 하자. n번째 비트와 n+1번째 비트의 값을 바꾸고, 0~(n-1)번째까지의 비트를 뒤집어주면 원하는 값이 된다.
  • 예를 들어 원래 수가 ????0111100 이었다면, 다음 큰 수는 ????1000111 이 된다.
• 문자열로 바꿔서 처리해도 간단하지만, 그냥 정수 상태에서 비트연산으로 처리해도 그리 복잡하지 않다.
• 마지막 비트가 '01'로 끝날때까지 원래수를 계속 오른쪽으로 쉬프트해준다. 쉬프트 해주면서 지워지는 비트중에서 1이었던 것의 갯수를 센다. 마지막 비트가 01이 되면, 1을 더해서 10으로 만든 다음 쉬프트했던 만큼 다시 왼쪽으로 쉬프트해서 원래 자리수와 동일하게 맞춰준다. 그 다음 하위 비트 x개를 1로 채우는 것은 (1«x) - 1 을 더해주면 된다
• 시간 복잡도는 2진수 표현의 자릿수이므로 O(logn)

"""Solution code for "Programmers 12911. 다음 큰 숫자".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/12911
- Solution link: http://www.teferi.net/ps/problems/programmers/12911
"""


def solution(n):
    shift = one_count = 0
    while n & 3 != 1:
        one_count += (n & 1)
        shift += 1
        n >>= 1
    answer = ((n + 1) << shift) + (1 << one_count) - 1
    return answer