Chương trình tìm số phép toán bit 1 tối thiểu để biến số thành 0 trong Python

Mô tả bài toán

Cho số n. Biến thành 0 bằng các phép: (1) đảo bit cuối cùng; (2) đảo bit i nếu bit i-1 = 1 và các bit i-2..0 = 0. Tìm số phép tối thiểu.

Ví dụ

n = 6 (binary 110) -> 4 phép: 110 -> 010 -> 011 -> 001 -> 000.

Giải thuật (Gray Code)

1. Chuyển n sang nhị phân.
2. Duyệt các bit: nếu bit trước = 1, đảo bit hiện tại.
3. Kết quả là số Gray code tương ứng, chuyển về thập phân.

Triển khai Python

def solve(n):
    n = list(map(int, bin(n)[2:]))
    m = []
    last = 0
    for d in n:
        if last == 1:
            d = 1 - d
        last = d
        m.append(d)
    m = ''.join(map(str, m))
    return int(m, 2)

n = 6
print(solve(n))

Đầu vào

6

Đầu ra

4