Python程序：查找与n具有相同设置位数的较大数字？

假设我们有一个数字n；我们必须找到具有与n相同的二进制形式中1的个数的下一个较小的较大数字。

因此，如果输入类似于n = 7，则输出将为11，因为7的二进制形式为0111，而下一个比7大的具有三个1的数字是11，其二进制形式为1011。

为了解决这个问题，我们将遵循以下步骤

  • copy := n，zeros := 0，ones := 0

  • 当copy不为0且copy为偶数时，执行

    • zeros := zeros + 1

    • copy = copy / 2

  • 当copy为奇数时，执行

    • ones := ones + 1

    • copy = copy / 2

  • right := ones + zeros

  • n := n OR (2^right)

  • n := n AND ( (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

更新于：2020年11月10日

136 次浏览

启动你的职业生涯

通过完成课程获得认证

开始
广告