二进制权重

题目描述

一个数的二进制权重被定义为一个十进制数表示为二进制数中 '1' 的个数。例如：

1 的二进制权重就是 1

1717 表示为二进制数为 11010110101，所以二进制权重为 7

现在给出一个正整数 N，返回最小的一个大于 N 并且二进制权重跟 N 相同的数。

输入描述：

输入一个数 N（1 <= N <= 1,000,000,000)

输出描述：

输出一个数，即为最小的一个大于 N 并且二进制权重跟 N 相同的数

输入例子：

1717

输出例子：

1718

自己的解答

正确但是超时的解答

def get_weight(number):
    return bin(number).count("1")

n = int(sys.stdin.readline().strip())
weight_n = get_weight(n)
for i in range(n + 1, 1000000000):
    if get_weight(i) == weight_n:
        print(i)

尝试优化的代码

由于自己当时笔试的时候写出来的版本只能通过 50% 的例子，所以下面先写个测试代码，再来改进自己的优化算法：

# 测试代码
#!/bin/env python3
# -*- coding: utf-8 -*-
# version: Python3.X
"""
这里的版本是一个超时但是正确的版本, 用这个版本来进行测试
"""
import unittest
from binary_weight import solve

__author__ = '__L1n__w@tch'


class TestBinaryWeightSolve(unittest.TestCase):
    def test_solve(self):
        for i in range(1, 1000000000):
            test_answer = solve(i)
            right_answer = TestBinaryWeightSolve.__right_answer(i)
            log_message = "i = {}, right: {}, my_answer: {}".format(i, right_answer, test_answer)
            self.assertEqual(right_answer, test_answer, log_message)

    @staticmethod
    def __right_answer(n):
        weight_n = TestBinaryWeightSolve.__get_weight(n)
        for i in range(n + 1, 1000000000):
            if TestBinaryWeightSolve.__get_weight(i) == weight_n:
                return i
        raise RuntimeError("[*] 自己的算法有问题了")

    @staticmethod
    def __get_weight(number):
        return bin(number).count("1")


if __name__ == "__main__":
    pass

通过测试的代码，不知道效率如何

#!/bin/env python3
# -*- coding: utf-8 -*-
# version: Python3.X
"""
20160924 发现原来只是 index == len(reverse_temp) - 1: 那里写错了, 改过来之后能够通过测试了
20160924 这是之前只能通过 50% 例子的版本, 现在利用测试找出算法缺陷
"""

__author__ = '__L1n__w@tch'


def get_weight(number):
    return bin(number).count("1")


def get_start_number(number):
    temp = bin(number)[2:]
    reverse_temp = temp[::-1]
    flag = False
    for index in range(len(reverse_temp)):
        # 查找到 0
        if reverse_temp[index] == "0" and flag == False:
            continue
        # 找到所要找的数字了
        if reverse_temp[index] == "1":
            flag = True
        # 找到最后一个数字了
        if index == len(reverse_temp) - 1:
            result = "1" + "0" * (index + 1)
            return int(result, 2)
        if reverse_temp[index] == "0" and flag == True:
            result = "0" * index + "1" + reverse_temp[index + 1:]
            result = result[::-1]
            return int(result, 2)


def solve(number):
    start_number = get_start_number(number)
    weight_n = get_weight(number)
    for i in range(start_number, 1000000000):
        if get_weight(i) == weight_n:
            return i


if __name__ == "__main__":
    solve(1)