假设我们有一个数字n;我们必须找到二进制数形式的最小的下一个较高的数字,该数字与n相同,为1。
因此,如果输入像n = 7,则输出将为11,因为二进制中的7为0111,接下来从7高到3的结果为11,二进制中为1011。
为了解决这个问题,我们将按照以下步骤操作:
复制:= n,零:= 0,一个:= 0
当复制不为0且复制为偶数时,执行
零:=零+ 1
复制=复制/ 2
虽然复制是奇怪的,但是
一个:=一个+ 1
复制=复制/ 2
右:=一+零
n:= n OR(2 ^对)
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