最接近的数

[编程题]最接近的数

热度指数：9007 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定正整数int x，将其用二进制表示，找到和它1的个数相同、且大小最接近的那两个二进制数(一个略大，一个略小)。请返回一个vector，代表这两个数的十进制表示（小的在前）。并保证答案存在。

测试样例：

返回：[1,4]

算法知识视频讲解

Python

Yannyezixin

思路：

取得略大的数：

c0 是拖尾0的个数，c1是紧邻拖尾0左方位为1的个数， p为最右边但非拖尾的0 等于 c0 + c1
把位p置为1
将p右方所有位置为零
在右方插入c1 - 1 个1

取得略小的数：

c1是拖尾1的个数， c0是紧邻拖尾1的左方一连串0的个数，p为最右边但非拖尾的1 等于c0 + c1
把位p置为0
将p右方所以位置清零
在p的紧邻右方插入c1 + 1个1

# -*- 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

发表于 2016-08-03 21:17:54 回复(1)