标签: 位运算
难度: Medium
下一个数。给定一个正整数，找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，一个略小）。
示例1:
输入：num = 2（或者0b10） 输出：[4, 1] 或者（[0b100, 0b1]）
示例2:
输入：num = 1 输出：[2, -1]
提示:
num的范围在[1, 2147483647]之间；- 如果找不到前一个或者后一个满足条件的正数，那么输出 -1。
Submission
运行时间: 22 ms
内存: 16.1 MB
class Solution:
def findClosedNumbers(self, num: int) -> List[int]:
digits = []
for i in range(31):
mask = 1 << i
digit = num & mask
if digit > 0:
digits.append(1)
else:
digits.append(0)
#print(digits)
#exit(0)
res1 = 0
i = 0
while i < 30:
if digits[i] == 1 and digits[i+1] == 0:
break
i += 1
# print(i)
digits1 = digits.copy()
if i == 30:
res1 = -1
else:
digits1[i+1] = 1
digits1[i] = 0
j = i-1
while j >= 0:
if digits1[j] == 0:
break
digits1[j] = 0
j -= 1
digits1[0:i-j-1] = [1] * (i-j-1)
#print(digits1)
#print(j)
res1 = self.digits_to_int(digits1)
res2 = 0
i = 1
while i < 30:
if digits[i] == 1 and digits[i-1] == 0:
break
i += 1
digits2 = digits.copy()
if i == 30:
res2 = -1
else:
digits2[i-1] = 1
digits2[i] = 0
j = 0
while j < i-1:
if digits2[j] == 0:
break
digits2[j] = 0
j += 1
digits2[i-j-1:i-1] = [1] * j
res2 = self.digits_to_int(digits2)
return [res1, res2]
def digits_to_int(self, digits: List[int]):
res = 0
for i, x in enumerate(digits):
mask = 0
if x > 0:
mask = 1 << i
res = res | mask
return res
Explain
题解首先将给定的数转换成二进制数组形式，便于处理。接着，为找出略大的数，从低位到高位找到第一个'01'的模式并将其交换成'10'，这会使得该数稍微变大。同时，为了保证增加最小，将所有位于该'01'模式之前的1都移到最低位。若找不到这样的模式，返回-1表示不存在这样的数。对于略小的数，寻找'10'模式并交换为'01'，再将前面的1移动到该'10'模式的左边，保持数尽可能大但小于原数。最后，提供一个辅助函数来将二进制数组转换回整数。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution:
def findClosedNumbers(self, num: int) -> List[int]:
digits = [] # 存储num的二进制表示
for i in range(31): # 固定31位，处理每一位
mask = 1 << i
digit = num & mask
digits.append(1 if digit > 0 else 0)
# 寻找略大的数
res1 = 0
i = 0
while i < 30: # 除最高位外，寻找'01'模式
if digits[i] == 1 and digits[i+1] == 0:
break
i += 1
digits1 = digits.copy()
if i == 30: # 未找到合适的'01'模式
res1 = -1
else:
digits1[i+1] = 1 # 交换'01'为'10'
digits1[i] = 0
j = i-1
while j >= 0 and digits1[j] == 1: # 移动前面的1到最低位
digits1[j] = 0
j -= 1
digits1[0:i-j-1] = [1] * (i-j-1)
res1 = self.digits_to_int(digits1) # 将数组转回整数
# 寻找略小的数
res2 = 0
i = 1
while i < 30: # 除最低位外，寻找'10'模式
if digits[i] == 1 and digits[i-1] == 0:
break
i += 1
digits2 = digits.copy()
if i == 30: # 未找到合适的'10'模式
res2 = -1
else:
digits2[i-1] = 1 # 交换'10'为'01'
digits2[i] = 0
j = 0
while j < i-1 and digits2[j] == 1: # 将前面的1尽量靠近i位
digits2[j] = 0
j += 1
digits2[i-j-1:i-1] = [1] * j
res2 = self.digits_to_int(digits2) # 将数组转回整数
return [res1, res2] # 返回结果
def digits_to_int(self, digits: List[int]): # 辅助函数：将二进制数组转回整数
res = 0
for i, x in enumerate(digits):
if x > 0:
res |= 1 << i
return res
Explore
在计算机中，通常使用32位来表示整数，其中有符号整数的最高位是符号位。在无符号整数的情况下，可以使用全部的32位来表示数值。这个解决方案中使用31位是为了保证处理的是一个没有符号的整数，避免涉及符号位带来的复杂性，同时确保结果在常用的整数表示范围内。如果使用更多的位数，可能会超出标准整数类型的范围，而使用更少的位数可能无法充分利用可用的数值范围。
在二进制数中，低位权重较小，高位权重较大。当我们将低位的'01'交换为'10'时，实际上是将一个较小的权重（0）替换为一个较大的权重（1），并且这个改变尽可能地小，因为它发生在尽可能低的位数上。这样，数值会略微增大，而增加的幅度也是最小的，这正是寻找略大的数的目的。数学上来说，这是因为我们通过最小的位改变来实现数值的最小增加。
在二进制数中，如果找不到'01'模式，意味着没有可能通过简单的位交换来获得一个略大的数，因为所有的'1'都在更高的位上，或者数值已经是连续的1后跟连续的0（如111...111000...000），这是一个递减或递增的极限情况。同理，找不到'10'模式意味着无法通过简单的位交换得到略小的数。在这种情况下，返回-1是表示没有可行的更大或更小的相邻数。理论上，除非增加额外的操作如位扩展或使用不同的数学方法，否则没有简单的替代方案来生成所需的略大或略小的数。