在Python中查找使整数为零的最少位操作的程序

假设我们有一个数字n，我们必须使用以下操作任意次数将其转换为0 –

• 在n的二进制表示中选择最右边的位。

• 当第（i-1）位为1且第（i-2）位到第0位为0时，更改n的二进制表示中的第i位。

所以最后我们需要找到将n转换为0所需的操作的最小数量。

因此，如果输入为n = 6，则输出将为4，因为最初6 =“110”，然后通过第二次操作将其转换为“010”，然后使用第一次操作转换为“011”，然后通过第二次操作转换为“001”，最后使用第一次操作转换为“000”。

为了解决这个问题，我们将按照以下步骤操作 –

• n：数字n的二进制位列表

• m：一个新列表

• last：0

• 对于n中的每个d，执行以下操作

  • 如果last与1相同，则
    • d = 1-d
  • 上一个：d

  • 在m的末尾插入d

• m：通过连接m的元素制作二进制数

• 以十进制形式返回m

示例

让我们看一下以下实现，以便更好地理解

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