给定正整数int x,将其用二进制表示,找到和它1的个数相同、且大小最接近的那两个二进制数(一个略大,一个略小)。请返回一个vector,代表这两个数的十进制表示(小的在前)。并保证答案存在。
测试样例:
2
返回:[1,4]
# -*- coding:utf-8 -*- class CloseNumber: def getCloseNumber(self, x): return self.getPrev(x), self.getNext(x) def getNext(self, n): c = n c0 = 0 c1 = 0 while c & 1 == 0 and c: c0 += 1 c >>= 1 while c & 1 == 1: c1 += 1 c >>= 1 if c0 + c1 >= 31 or c0 + c1 == 0: return False p = c0 + c1 # 翻转最右边非拖尾0 n |= (1 << p) # 将p右方的所有为清零 n &= ~((1 << p) - 1) # 在右方插入(c1 - 1)个1 n |= (1 << (c1 - 1)) - 1 return n def getPrev(self, n): c = n c0 = 0 c1 = 0 while c & 1 == 1: c1 += 1 c >>= 1 if c == 0: return -1 while c & 1 == 0 and c: c0 += 1 c >>= 1 p = c0 + c1 # 位0到p位清零 n &= (~0) << (p + 1) # 在p后面插入c1 + 1个1 n |= ((1 << (c1 + 1)) - 1) << (c0 - 1) return n