สมมติว่าเรามีตัวเลข n; เราต้องหาจำนวนที่สูงกว่าถัดไปที่เล็กที่สุดด้วยจำนวนเดียวกันของ 1s เป็น n ในรูปแบบไบนารี
ดังนั้น หากอินพุตเท่ากับ n =7 เอาต์พุตจะเป็น 11 เนื่องจาก 7 ในไบนารีคือ 0111 และสูงกว่าถัดไปจาก 7 โดยมีสามตัวคือ 11 ซึ่งเท่ากับ 1011 ในไบนารี
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
-
สำเนา :=n, ศูนย์ :=0, ตัว :=0
-
ในขณะที่การคัดลอกไม่ใช่ 0 และการคัดลอกจะเท่ากัน ทำ
-
ศูนย์ :=ศูนย์ + 1
-
สำเนา =สำเนา / 2
-
-
ในขณะที่การคัดลอกเป็นเลขคี่ให้ทำ
-
อัน :=อัน + 1
-
สำเนา =สำเนา / 2
-
-
ขวา :=หนึ่ง + ศูนย์
-
n :=n OR (2^ขวา)
-
n :=n AND invert of ((2^right) - 1)
-
n :=n OR((2 ^ (ones - 1)) - 1
-
กลับ n
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
ตัวอย่าง
class Solution: def solve(self, n): copy = n zeros = 0 ones = 0 while copy and not copy & 1: zeros += 1 copy >>= 1 while copy & 1: ones += 1 copy >>= 1 right = ones + zeros n |= 1 << right n &= ~((1 << right) - 1) n |= (1 << ones - 1) - 1 return n ob = Solution() n = 7 print(ob.solve(n))
อินพุต
7
ผลลัพธ์
11
