Python으로 이진수 1의 개수가 같은 바로 다음 큰 수 찾는 방법

숫자 n이 하나 주어졌다고 가정해 보겠습니다. 우리가 해야 할 일은 이진수 표현에서 1의 개수(세트 비트)가 n과 정확히 동일하면서, n보다 큰 수 중 가장 작은 수를 찾는 것입니다.

예시로 이해하기

예를 들어 입력이 n = 7이라면 결과는 11이 됩니다.

• 7의 이진수 표현: 0111 → 1이 세 개
• 1이 세 개인 수 중 7보다 큰 가장 작은 수: 1011, 즉 십진수 11

해결 알고리즘

이 문제는 비트 조작(bit manipulation) 기법을 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 n의 이진수에서 가장 오른쪽에 있는 연속된 1의 그룹을 찾아, 해당 위치의 패턴을 재배치하는 것입니다. 절차는 다음과 같습니다.

1. 초기화: copy = n, zeros = 0, ones = 0으로 설정합니다.
2. 뒤따르는 0의 개수 세기: copy가 0이 아니고 짝수인 동안 zeros를 1씩 증가시키고 copy를 오른쪽으로 한 비트씩 시프트합니다.
3. 연속된 1의 개수 세기: copy가 홀수인 동안 ones를 1씩 증가시키고 copy를 계속 오른쪽으로 시프트합니다.
4. 경계 위치 계산: right = ones + zeros로, 변경이 일어날 비트 위치를 구합니다.
5. 비트 올리기: n |= (1 << right)로 right 위치의 비트를 1로 설정합니다.
6. 하위 비트 지우기: n &= ~((1 << right) - 1)로 right 위치 아래의 모든 비트를 0으로 만듭니다.
7. 1 채우기: n |= (1 << (ones - 1)) - 1로 최하위 비트 쪽에 (ones - 1)개의 1을 채워 넣습니다.
8. 결과 반환: 최종 n을 반환합니다.

이 과정을 거치면 1의 총 개수는 그대로 유지되면서, 가장 왼쪽으로 밀어낼 수 있는 1이 한 자리 위로 이동하고 나머지 1들은 최대한 오른쪽으로 몰리게 됩니다. 그 결과가 바로 '다음으로 큰 수'입니다.

Python 구현 코드

class Solution:
    def solve(self, n):
        copy = n
        zeros = 0
        ones = 0
        while copy and not copy & 1:
            zeros += 1
            copy >>= 1
        while copy & 1:
            ones += 1
            copy >>= 1
        right = ones + zeros
        n |= 1 << right
        n &= ~((1 << right) - 1)
        n |= (1 << ones - 1) - 1
        return n

ob = Solution()
n = 7
print(ob.solve(n))

실행 결과

입력:

7

출력:

11

마무리

이 알고리즘은 반복문이 n의 비트 길이에 비례하여 실행되므로 시간 복잡도는 O(log n)입니다. 추가적인 메모리 없이 비트 연산만으로 해결되기 때문에 매우 효율적이며, 조합론에서 자주 등장하는 '다음 조합(next combination)' 문제와도 본질적으로 같은 원리입니다.