Pythonで整数をゼロにするための最小1ビット演算を見つけるプログラム

数nがあるとすると、次の操作を何度でも使用して、それを0に変換する必要があります-

• nのバイナリ表現の右端のビットを選択します。

• （i-1）番目のビットが1に設定され、（i-2）番目から0番目のビットが0に設定されている場合は、nのバイナリ表現のi番目のビットを変更します。

したがって、最後に、nを0に変換するために必要な操作の最小数を見つける必要があります。

したがって、入力がn =6の場合、最初は6 ="110"であるため、出力は4になります。次に、2番目の操作で「010」に変換し、最初の操作で「011」に変換してから、「 001 "は2番目の操作を使用し、最後に最初の操作を使用して"000"に変換します。

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

• n：=数値nのバイナリビットのリスト

• m：=新しいリスト

• 最後：=0

• nの各dについて、実行します

  • lastが1と同じ場合、

    • d：=1-d

  • 最後：=d

  • mの最後にdを挿入します

• m：=mの要素を結合して2進数を作成する

• mを10進数で返す

例

理解を深めるために、次の実装を見てみましょう

def solve(n):
   n=list(map(int,bin(n)[2:]))
   m=[]
   last=0
   for d in n:
      if last==1:
         d=1-d
      last=d
      m.append(d)
   m=''.join(map(str,m))
   return int(m,2)

n = 6
print(solve(n))

入力

"95643", "45963"

出力

4