leetcode
leetcode 2801 ~ 2850
整数转换

整数转换

难度:

标签:

题目描述

Write a function to determine the number of bits you would need to flip to convert integer A to integer B.

Example1:

 Input: A = 29 (0b11101), B = 15 (0b01111)
 Output: 2

Example2:

 Input: A = 1,B = 2
 Output: 2

Note:

  1. -2147483648 <= A, B <= 2147483647

代码结果

运行时间: 26 ms, 内存: 16.0 MB


/*
 * Problem: Determine the number of bits needed to convert integer A to integer B.
 * Approach: Use Java Streams to count the number of differing bits.
 * XOR A and B, convert to binary string, and count '1's.
 */

import java.util.stream.Stream;

public class BitConversionStream {
    public static int countBitsToConvert(int A, int B) {
        return (int) Stream.of(Integer.toBinaryString(A ^ B).split(""))
                .filter(bit -> bit.equals("1"))
                .count(); // Count the number of '1's in the binary string
    }

    public static void main(String[] args) {
        System.out.println(countBitsToConvert(29, 15)); // Output: 2
        System.out.println(countBitsToConvert(1, 2)); // Output: 2
    }
}

解释

方法:

这个题解利用异或操作来找出两个整数在二进制表示中不同的位。异或操作的特点是相同的位结果为0,不同的位结果为1。因此,将A和B进行异或操作后,不同位上的结果将为1。然后,题解通过遍历这个结果的每一位(总共32位,因为Python中整数是32位),统计值为1的位的数量,这个数量就是A需要改变的位数才能变成B。

时间复杂度:

O(1)

空间复杂度:

O(1)

代码细节讲解

🦆
题解中提到需要遍历32位来统计不同的位数,但是对于负数是否需要特别处理或者有不同的计算方式?
在Python中,整数使用补码形式表示,这意味着负数的最高位(符号位)为1,而正数为0。当使用异或操作时,两个数的对应位如果不同,则结果位为1,否则为0,无论这些位是符号位还是数值位。因此,对于负数,我们不需要特别的处理方式。异或操作本身已经考虑了补码的表示方式,确保了不同的位能够被正确地标记和统计。
🦆
你是如何确定使用异或操作来找出两个整数不同的位的,这种方法是否适用于所有整数包括负数?
异或操作的定义是,两个位相同则结果为0,不同则为1。这一特性使得它非常适合用来确定两个整数在哪些位上有差异。由于整数(包括负数)在计算机中是以补码形式存储的,异或操作直接应用于这些补码。因此,这种方法适用于所有整数,包括负数,因为它直接比较的是补码中的位,无需额外转换或处理。
🦆
题解提到了使用32次循环来检查每一位,这是否意味着算法的效率与输入的大小无关?
是的,此算法的效率与输入的具体值大小无关,因为无论输入的数值大小如何,异或操作后的结果总是一个32位的整数(在Python中是32位),我们需要做的是检查这32位中有多少位是1。因此,算法的时间复杂度是常数时间O(1),即只与位的数量(这里是32位)有关,与具体的数值大小无关。

相关问题