Python刷题:集合S(k)求|x-y|最小时的x和y(二进制)

Python刷题:集合S(k)求|x-y|最小时的x和y(二进制)[Python基础]

题目描述

对于64位或32位的无符号整数x,我们在它的二进制表示中,把1的个数称为x的权重。例如x=7,它的二进制表示为0b111,由于有3个1,所以x的权重就是3。用S(k)表示64位或32位整数中,权重为k的所有整数的集合,其中k不等于0、32、64。现给定一个整数x,假定它属于集合S(k),要求找出另一个属于S(k)的整数y,使得|x-y|的值最小。

解题思路

解题方法:可以先使用穷举法,使k等于一个较小的数,比如k=3,假定x=0b1011,然后列举一些同样k=3的数字作为y,可以发现|x-y|最小时的y=0b1101,可以再假定x为其他一些值,并找出对应的|x-y|最小时的y,可以发现这样一个简单的规律:x对应的y其实就是在x的二进制表示中从右往左遍历,找到两个值不同的比特位,然后交换这两个比特位的值就得到了y的二进制表示。

思考:由于这个规律只是通过简单的几个例子得出,不一定保证是正确的解题方法,所以可以再思考一下这个方法的可行性:想要两个数的差的绝对值最小,就需要这两个数尽可能相近,即二进制位上各个位置上的值要尽可能相同,而又由于需要权重相同,所以只能将其中一个0变为1,另一个1变为0,即将x中的其中一组0和1进行交换,而这样变换之后的相减操作,想要两个值的差值最小,交换的这两个位置就必须尽可能相近且应该是从最低位开始查找,而最相近的两个0和1无疑就是相邻的0和1了。

解题代码

def func(x):
    """假定x为64位整数"""

    # 从低位向高位扫描
    for i in range(64):
        # 找出相邻的一组0和1的位置
        if ((x >> i) & 1) != ((x >> (i + 1)) & 1):
            # 交换两个位置的值
            return x ^ ((1 << i) | (1 << (i + 1)))


print(bin(func(0b1011)))  # 输出: 0b1101

总结

像这类题目,光是凭想象短时间是不太能找出规律的,所以可以先使用穷举法通过一些简单的例子看看是否能找出规律,找到规律后需要再思考下这个规律是否满足题目的要求,当然如果时间紧迫可以先写出算法,后面有时间再来完善和验证算法的正确性。交换x中指定两个位置i和j的比特位使用公式x ^ ((1 << i) | (1 << j))即可。

题目及解题算法来自:书籍《Python程序员面试宝典》。

hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » Python刷题:集合S(k)求|x-y|最小时的x和y(二进制)