Chương trình tìm số lớn hơn tiếp theo có cùng số bit 1 trong Python

Cho số nguyên n. Tìm số nguyên dương nhỏ nhất lớn hơn n có cùng số bit 1 trong biểu diễn nhị phân.

Ví dụ

n = 7 (nhị phân 0111, 3 bit 1)

Số tiếp theo có 3 bit 1: 11 (nhị phân 1011) → kết quả: 11.

Thuật toán (Bit Manipulation - Next Higher Number with Same Popcount)

1. Đếm số bit 0 liên tiếp ở cuối (zeros) và số bit 1 liên tiếp sau đó (ones).
2. Vị trí bit cần set: right = ones + zeros.
3. Set bit tại right: n |= (1 << right).
4. Clear tất cả bit bên phải right: n &= ~((1 << right) - 1).
5. Set ones-1 bit thấp nhất: n |= (1 << (ones - 1)) - 1.

Triển khai Python

class Solution:
    def solve(self, n):
        c = n
        zeros = 0
        ones = 0
        
        # Đếm trailing zeros
        while c and (c & 1) == 0:
            zeros += 1
            c >>= 1
        
        # Đếm trailing ones
        while c & 1:
            ones += 1
            c >>= 1
        
        # Nếu n dạng 111...1100...00 thì không có số lớn hơn cùng popcount
        if zeros + ones == 0 or zeros + ones == n.bit_length():
            return -1  # hoặc xử lý theo yêu cầu
        
        right = ones + zeros
        n |= 1 << right           # Set bit right
        n &= ~((1 << right) - 1)  # Clear bits bên phải
        n |= (1 << (ones - 1)) - 1  # Set (ones-1) bit thấp nhất
        
        return n

# Test
ob = Solution()
print(ob.solve(7))    # 11 (0111 -> 1011)
print(ob.solve(12))   # 17 (1100 -> 10001)
print(ob.solve(5))    # 6  (0101 -> 0110)

Độ phức tạp

• Thời gian: O(log n) - số bit của n.
• Không gian: O(1).

Đây là thuật toán "Next Higher Number with Same Number of Set Bits" (snoob).