Kiểm tra số n có phải lũy thừa của d (d là lũy thừa của 2) trong Python

Cho hai số n và x, trong đó x là lũy thừa của 2. Kiểm tra xem n có phải là lũy thừa của x hay không.

Ví dụ: n = 32768, x = 32 → True vì 32768 = 32³.

Ý tưởng

• Nếu n là lũy thừa của 2 (kiểm tra bằng n & (n-1) == 0).
• Đếm số lần chia 2 để về 1 → cnt (số mũ của 2 trong n).
• Tìm số mũ của 2 trong x (gọi là k).
• n là lũy thừa của x khi cnt % k == 0.

Triển khai

def find_pow_of_2(n):
    """Trả về số mũ k sao cho n = 2^k (n phải là lũy thừa của 2)"""
    return (1 + find_pow_of_2(n // 2)) if n > 1 else 0

def solve(n, c):
    cnt = 0
    if n and (n & (n - 1)) == 0:  # n là lũy thừa của 2
        while n > 1:
            n >>= 1
            cnt += 1
        return cnt % find_pow_of_2(c) == 0
    return False

n = 32768
x = 32
print(solve(n, x))  # True

Đầu vào / Đầu ra

Input: 32768, 32
Output: True

Giải thích thêm: find_pow_of_2 dùng đệ quy; có thể thay bằng c.bit_length() - 1 (Python 3) cho ngắn gọn.