Chương trình tìm số cao hơn với cùng số bit đặt như n trong Python?

Giả sử chúng ta có một số n; chúng ta phải tìm số cao hơn tiếp theo nhỏ nhất có cùng số 1 với n ở dạng nhị phân.

Vì vậy, nếu đầu vào là n =7, thì đầu ra sẽ là 11, vì 7 trong nhị phân là 0111 và cao hơn tiếp theo từ 7 với ba cái sẽ là 11, 1011 trong nhị phân.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• copy:=n, số không:=0, số không:=0

• trong khi bản sao không phải là 0 và bản sao là số chẵn, thực hiện

  • số không:=số không + 1

  • copy =copy / 2

• trong khi bản sao là kỳ quặc, hãy làm

  • những cái:=những cái + 1

  • copy =copy / 2

• right:=ones + zeros

• n:=n HOẶC (2 ^ phải)

• n:=n AND đảo ngược của ((2 ^ phải) - 1)

• n:=n HOẶC ((2 ^ (cái - 1)) - 1

• trả lại n

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Ví dụ

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

Đầu vào

7

Đầu ra

11