Python - Dãy 1 liên tiếp dài nhất trong biểu diễn nhị phân

Cho số không âm n, tìm độ dài dãy 1 liên tiếp dài nhất trong biểu diễn nhị phân của n.

Ví dụ

Input: n = 1469
Output: 4
Giải thích: 1469 = 10110111101₂, có 4 bit 1 liên tiếp (1111).

Thuật toán: Thao tác bit (Brian Kernighan mở rộng)

Ý tưởng: n & (n << 1) sẽ xóa bit 1 cuối cùng của mỗi dãy 1 liên tiếp. Lặp cho đến khi n=0, đếm số lần lặp.

n        = 10110111101
n << 1   = 01101111010
n & (n<<1)= 00100111000  (xóa bit 1 cuối mỗi cụm)

Mã Python

def solve(n):
    count = 0
    while n != 0:
        n = n & (n << 1)
        count += 1
    return count

# Test
n = 1469
print(solve(n))  # Output: 4

Phân tích độ phức tạp

• Thời gian: O(k) - k = độ dài dãy 1 liên tiếp dài nhất (≤ log₂n)
• Không gian: O(1)

So sánh

• Cách thông thường: chuyển sang chuỗi nhị phân, split by '0' → O(log n) thời gian, O(log n) không gian
• Cách bitwise: O(k) thời gian, O(1) không gian - nhanh hơn khi dãy 1 ngắn

Mẹo: Đây là kỹ thuật bit manipulation cổ điển, thường gặp trong phỏng vấn và lập trình thi đấu.