Pythonのnと同じセットビット数でより高い数を見つけるプログラム？

数nがあるとします。バイナリ形式のnと同じ数の1で、次に大きい最小の数を見つける必要があります。

したがって、入力がn =7の場合、出力は11になります。これは、バイナリの7が0111であり、3つの7から次に高い値が11になり、バイナリの1011になります。

これを解決するには、次の手順に従います。

• コピー：=n、ゼロ：=0、1：=0

• コピーが0ではなく、コピーが偶数である場合は、実行してください

  • ゼロ：=ゼロ+ 1

  • コピー=コピー/2

• コピーは奇妙ですが、実行してください

  • ones：=ones + 1

  • コピー=コピー/2

• 右：=1と0

• 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