โปรแกรมหาการดำเนินการบิต 1 น้อยที่สุดเพื่อทำให้จำนวนเป็นศูนย์ใน Python

มีจำนวน n ต้องทำให้เป็น 0 ด้วยการดำเนินการ:

1. เลือกบิตขวาสุด (LSB) กลับค่า
2. กลับบิตที่ i ถ้าบิต i-1 เป็น 1 และบิต i-2 ถึง 0 เป็น 0 ทั้งหมด

หาจำนวนการดำเนินการน้อยที่สุด

ตัวอย่าง: n=6 (110) ผลลัพธ์ 4 (110→010→011→001→000)

วิธีแก้ปัญหา (Gray Code / Binary Reflection)

1. แปลง n เป็นบิต
2. สร้าง m โดย: m[i] = n[i] XOR n[i-1] (prefix XOR)
3. ค่าของ m ในฐานสิบคือคำตอบ

ตัวอย่างโค้ด

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))

อินพุต

6

เอาต์พุต

4