标签: 位运算
难度: Easy
整数转换。编写一个函数，确定需要改变几个位才能将整数A转成整数B。
示例1:
输入：A = 29 （或者0b11101）, B = 15（或者0b01111） 输出：2
示例2:
输入：A = 1，B = 2 输出：2
提示:
- A，B范围在[-2147483648, 2147483647]之间
Submission
运行时间: 26 ms
内存: 16.0 MB
class Solution:
def convertInteger(self, A: int, B: int) -> int:
x = A ^ B
result = 0
for i in range(32):
result += 1 if x & (1<<i) != 0 else 0
return result
Explain
这个题解利用异或操作来找出两个整数在二进制表示中不同的位。异或操作的特点是相同的位结果为0，不同的位结果为1。因此，将A和B进行异或操作后，不同位上的结果将为1。然后，题解通过遍历这个结果的每一位（总共32位，因为Python中整数是32位），统计值为1的位的数量，这个数量就是A需要改变的位数才能变成B。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution:
def convertInteger(self, A: int, B: int) -> int:
x = A ^ B # A和B进行异或操作, 不同的位将被标记为1
result = 0 # 用于计数不同位的数量
for i in range(32): # 对于32位整数的每一位
result += 1 if x & (1<<i) != 0 else 0 # 如果第i位是1, 则计数加1
return result # 返回不同位的总数
Explore
在Python中，整数使用补码形式表示，这意味着负数的最高位（符号位）为1，而正数为0。当使用异或操作时，两个数的对应位如果不同，则结果位为1，否则为0，无论这些位是符号位还是数值位。因此，对于负数，我们不需要特别的处理方式。异或操作本身已经考虑了补码的表示方式，确保了不同的位能够被正确地标记和统计。
异或操作的定义是，两个位相同则结果为0，不同则为1。这一特性使得它非常适合用来确定两个整数在哪些位上有差异。由于整数（包括负数）在计算机中是以补码形式存储的，异或操作直接应用于这些补码。因此，这种方法适用于所有整数，包括负数，因为它直接比较的是补码中的位，无需额外转换或处理。
是的，此算法的效率与输入的具体值大小无关，因为无论输入的数值大小如何，异或操作后的结果总是一个32位的整数（在Python中是32位），我们需要做的是检查这32位中有多少位是1。因此，算法的时间复杂度是常数时间O(1)，即只与位的数量（这里是32位）有关，与具体的数值大小无关。