โปรแกรมหา Bitwise AND ของช่วงตัวเลขใน Python

สมมติว่าเรามีค่า start และ end เราต้องหา Bitwise AND ของตัวเลขทั้งหมดในช่วง [start, end] (รวมทั้งสองข้าง)

เช่น ถ้าอินพุตคือ start = 8, end = 12 ผลลัพธ์จะเป็น 8 เพราะ 8 คือ 1000 ในไบนารี และ 12 คือ 1100 ดังนั้น 1000 AND 1001 AND 1010 AND 1011 AND 1100 = 1000 ซึ่งคือ 8

ขั้นตอนการแก้ปัญหา

1. n := end - start + 1
2. x := 0
3. สำหรับ b ในช่วง 31 ลงถึง 0:
   • ถ้า 2^b < n ออกจากลูป
   • ถ้า 2^b AND start AND end ไม่เป็นศูนย์ ให้ x := x + (2^b)
4. คืนค่า x

ตัวอย่างการใช้งาน

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

start = 8
end = 12
print(solve(start, end))

อินพุต

8, 12

เอาต์พุต

8