Chương trình tính bitwise AND của dải số nguyên Python

Cho hai giá trị start và end, tính bitwise AND của tất cả số trong khoảng [start, end] (bao gồm cả hai đầu).

Ví dụ: start=8 (1000), end=12 (1100) → 1000 & 1001 & 1010 & 1011 & 1100 = 1000 = 8.

Giải thuật (Phân tích bit)

1. n = end - start + 1 (số lượng số trong khoảng)
2. Duyệt bit từ 31 xuống 0:
   • Nếu 2^b < n: break (bit này chắc chắn sẽ có cả 0 và 1 trong khoảng)
   • Nếu bit b của cả start và end đều là 1 → giữ bit này trong kết quả

Ví dụ triển khai

def solve(start, end):
    n = end - start + 1
    x = 0
    for b in range(31, -1, -1):
        if (1 << b) < n:
            break
        if (1 << b) & start & end:
            x += 1 << b
    return x

print(solve(8, 12))

Đầu vào

8, 12

Đầu ra

8