โปรแกรมหาตัวเลขที่มากกว่าและมีจำนวนบิต 1 เท่ากับ n ใน Python

สมมติว่าเรามีตัวเลข n ต้องหาตัวเลขที่มากกว่า n น้อยที่สุดที่มีจำนวนบิต 1 ในรูปแบบทวิณัติเท่ากับ n

ตัวอย่าง

อินพุต: n = 7 (binary 0111)

เอาต์พุต: 11 (binary 1011) ทั้งคู่มีบิต 1 สามตัว

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

ใช้อัลกอริทึม bit manipulation มาตรฐาน (next higher number with same number of set bits):

1. copy = n, zeros = 0, ones = 0
2. นับศูนย์ต่อท้าย: while copy and not copy & 1: zeros++, copy >>= 1
3. นับบิต 1 ติดต่อกันหลังศูนย์: while copy & 1: ones++, copy >>= 1
4. right = ones + zeros
5. n |= 1 << right (ตั้งบิตที่ right)
6. n &= ~((1 << right) - 1) (ล้างบิตขวาของ right)
7. n |= (1 << (ones - 1)) - 1 (ตั้งบิต 1 จำนวน ones-1 ตัวทางขวาสุด)
8. คืนค่า n

การนำไปใช้ใน Python

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