跳转至

面试题 05.06. 整数转换

题目描述

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

示例1:

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

示例2:

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

提示:

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

解法

方法一：位运算

思考

要把 \(A\) 变成 \(B\)，即翻转不相同的位。逐位比较 \(32\) 次可行。

不相同的位恰是 \(A\oplus B\) 中的 \(1\)，故问题化为求异或的汉明重量。

先与 \(0xFFFFFFFF\) 截成无符号 \(32\) 位，避免语言中负数算术移位的差异，再 bit_count。

我们将 A 和 B 进行异或运算，得到的结果的二进制表示中 \(1\) 的个数即为需要改变的位数。

时间复杂度 \(O(\log n)\)，其中 \(n\) 为 A 和 B 的最大值。空间复杂度 \(O(1)\)。

1
2
3
4
5
class Solution:
    def convertInteger(self, A: int, B: int) -> int:
        A &= 0xFFFFFFFF
        B &= 0xFFFFFFFF
        return (A ^ B).bit_count()

1
2
3
4
5
class Solution {
    public int convertInteger(int A, int B) {
        return Integer.bitCount(A ^ B);
    }
}

1
2
3
4
5
6
7
class Solution {
public:
    int convertInteger(int A, int B) {
        unsigned int c = A ^ B;
        return __builtin_popcount(c);
    }
};

1
2
3
func convertInteger(A int, B int) int {
    return bits.OnesCount32(uint32(A ^ B))
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function convertInteger(A: number, B: number): number {
    let res = 0;
    while (A !== 0 || B !== 0) {
        if ((A & 1) !== (B & 1)) {
            res++;
        }
        A >>>= 1;
        B >>>= 1;
    }
    return res;
}

1
2
3
4
5
impl Solution {
    pub fn convert_integer(a: i32, b: i32) -> i32 {
        (a ^ b).count_ones() as i32
    }
}

1
2
3
4
5
class Solution {
    func convertInteger(_ A: Int, _ B: Int) -> Int {
        return (Int32(A) ^ Int32(B)).nonzeroBitCount
    }
}

评论