程序员面试金典 - 面试题 05.06. 整数转换

题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

整数转换。编写一个函数，确定需要改变几个位才能将整数 A 转成整数 B。

示例 1:

• 输入：A = 29 （或者 0b11101）, B = 15（或者 0b01111）
• 输出：2

示例 2:

• 输入：A = 1，B = 2
• 输出：2

提示:

• A，B 范围在[-2147483648, 2147483647]之间

题目思考

1. 如何找到 A 与 B 有几位不同?

解决方案

思路

• 想要得到 A 与 B 有几位不同, 我们不难发现异或操作就可以做到这一点
• A 异或 B 的结果中, 某一位上若 A 与 B 的数字不同, 则该位为 1, 否则为 0
• 接下来就可以将问题转换成求 1 的个数
• 求 1 的个数在我之前的文章剑指 Offer 15. 二进制中 1 的个数中已经有详细方法与解释, 这里不再赘述, 针对本题, 我们采用 while 循环 + n & (n-1)快速得到它
• 另外特别注意, Python 存储的数字不只 32 位, 如果遇到正数和负数求异或时, 超出 32 位的部分都会变成 1, 所以我们在异或之后需要额外与 0xFFFFFFFF 求交, 保证结果限定在 32 位整数范围内, 避免在求 1 的数目时无限循环

复杂度

• 时间复杂度 O(logN): 一次异或操作复杂度 O(1), 查找 1 的个数时最多有 32 个 1, 此处复杂度是 O(logN)
• 空间复杂度 O(1): 只使用了几个变量

代码

Python 3

class Solution:
    def convertInteger(self, A: int, B: int) -> int:
        # 求异或+计算1的个数
        res = (A ^ B) & 0xFFFFFFFF
        cnt = 0
        while res:
            res = res & (res - 1)
            cnt += 1
        return cnt

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊