Chương trình tìm khoảng cách lớn nhất giữa hai bit 1 liên tiếp trong nhị phân bằng Python

Cho số N. Tìm khoảng cách lớn nhất giữa hai bit 1 liên tiếp trong biểu diễn nhị phân. Nếu không có hai bit 1, trả về 0.

Ví dụ: 71 → nhị phân 1000111. Khoảng cách giữa bit 1 đầu tiên và bit 1 thứ hai là 4 (vị trí 6 và 2). Các bit 1 khác cách nhau 1. Kết quả 4.

Thuật toán giải quyết

• Chuyển N sang nhị phân, bỏ tiền tố "0b", chuyển thành list ký tự.
• Max=0, C=0 (vị trí 1 trước), S=0 (vị trí 1 hiện tại), Flag=False.
• Duyệt i qua các bit:
  • Nếu bit='1' và C=0 và Flag=False: C=i, Flag=True (bit 1 đầu tiên).
  • Nếu bit='1' và Flag=True: S=i, Max=max(Max, |S-C|), C=S.
• Trả về Max.

Ví dụ triển khai

def solve(N):
    B = bin(N).replace('0b', '')
    K = list(B)
    Max = 0
    C = 0
    S = 0
    Flag = False
    for i in range(len(K)):
        if K[i] == '1' and C == 0 and Flag is False:
            C = i
            Flag = True
        elif K[i] == '1' and Flag:
            S = i
            if Max < abs(S - C):
                Max = abs(S - C)
            C = S
    return Max

n = 71
print(solve(n))

Đầu vào

71

Đầu ra

4