Java 中不匹配位的数量

2024年9月10日 | 阅读 9 分钟

在本教程中，我们将讨论 Java 中的不匹配位数问题。在此问题中，给出两个数字（f1 和 f2）。我们的任务是比较两个数字的二进制表示形式时，找出不匹配的位数。假设每个数字都适合 8 位。

示例 1

输入

int f1 = 9

int f2 = 15

输出

不匹配的总位数为 2。

解释

数字 9 在 8 位中的二进制表示是 00001001，数字 15 在 8 位中的二进制表示是 00001111。如果我们从左到右比较这两个二进制表示，我们会发现前五位匹配。第六位和第七位不匹配，因为数字 9 的这两位都是零，而数字 15 的这两位都是一。因此，有两位不匹配。所以，输出是 2。

示例 2

输入

int f1 = 32

int f2 = 31

输出

不匹配的总位数为 6。

解释

数字 32 在 8 位中的二进制表示是 00100000，数字 31 在 8 位中的二进制表示是 00011111。如果我们从左到右比较这两个二进制表示，我们会发现前两位匹配。之后，直到第八位都存在不匹配。数字 32 的第三位是 1，数字 31 的第三位是 0，而对于其余的其他位，数字 32 的值为 0，数字 31 的值为 1。因此，有 6 位不匹配。所以，输出是 6。

示例 3

输入

int f1 = 40

int f2 = 40

输出

不匹配的总位数为 0。

解释

由于两个数字相同，它们的二进制表示也将相同。因此，不匹配的位数将为零。所以，输出是 0。

简单方法

最简单的方法是首先将两个数字（f1 和 f2）转换为它们的二进制表示。然后将它们的二进制表示存储在数组列表中（一个用于 f1 的二进制表示，另一个用于 f2 的二进制表示）。之后，使用循环，我们可以比较这些位并找出答案。请看以下程序。

文件名: MismatchingBits.java

// importing ArrayList as it is 
// required by the program
import java.util.ArrayList;

public class MisMatchingBits
{
// a method that finds the number of mismatching bits
// in the numbers a and b
public int countMisMatchBit(int a, int b)
{
    // handling the base case
    // if both the numbers are the same, then 
    // the number of mismatching bits is zero.
    if(a == b)
    {
        return 0;
    }
    
    // for storing the count of the mismatching bits
    int countMisMatchBits = 0;
    
    // two lists that represent the binary representation in reverse order
    // of the numbers a and b in 8 bits
    ArrayList<Integer> list1 = new ArrayList<Integer>();
    ArrayList<Integer> list2 = new ArrayList<Integer>();
    
    // loop that converts the number a
    // from decimal (base-10) to binary (base-2)
    while(a != 0)
    {
        int n = a % 2;
        a = a / 2;
        list1.add(n);
    }
    
    // loop that converts the number b
    // from decimal (base-10) to binary (base-2)
    while(b != 0)
    {
        int n = b % 2;
        b = b / 2;
        list2.add(n);
    }
    
    // the lists size have to be 8
    
    // if the size of the lists is less than 8 and 
    // increase the size upto 8 by adding 0 to it.
    while(list1.size() != 8)
    {
        list1.add(0);
    }
    
    while(list2.size() != 8)
    {
        list2.add(0);
    }
    
    // loop that makes the comparison of bits of the numbers a and b
    for(int i = 0; i < 8; i++)
    {
        if(list1.get(i) != list2.get(i))
        {
            // mismatch occurred. Hence, increase the count by 1
            countMisMatchBits = countMisMatchBits + 1;
        }
    }
    
    // return the count
    return countMisMatchBits;
}
// main method
public static void main(String[] argvs) 
{
    // creating an object of the class MisMatchingBits
    MisMatchingBits obj = new MisMatchingBits( );
    
    // the two input numbers
    int f1 = 9;
    int f2 = 15;
    
    int ans = obj.countMisMatchBit(f1, f2);
    System.out.println("The number of mismatching bits for the numbers " + f1 + " and " + f2 + " is: " + ans);
    System.out.println( );
    
    
    // the two input numbers
    f1 = 32;
    f2 = 31;
    
    ans = obj.countMisMatchBit(f1, f2);
    System.out.println("The number of mismatching bits for the numbers " + f1 + " and " + f2 + " is: " + ans);
    
    System.out.println( );
    
    
    // the two input numbers
    f1 = 40;
    f2 = 40;
    
    ans = obj.countMisMatchBit(f1, f2);
    System.out.println("The number of mismatching bits for the numbers " + f1 + " and " + f2 + " is: " + ans);
}

}

输出

The number of mismatching bits for the numbers 9 and 15 is: 2

The number of mismatching bits for the numbers 32 and 31 is: 6

The number of mismatching bits for the numbers 40 and 40 is: 0

复杂度分析: 程序中有四个 while 循环和一个 for 循环。在这五个循环中，两个 while 循环和一个 for 循环都只运行常数时间。最后两个 while 循环和 for 循环在最坏情况下需要 O(8) 时间，这是常数。因此，程序的整体时间复杂度取决于前两个 while 循环。第一个 while 循环需要 O(dig1) 时间，第二个循环需要 O(dig2) 时间。因此，程序的整体时间复杂度为 O(dig1 + dig2)，其中 dig1 是数字 f1 中存在的总位数，dig2 是数字 f2 中存在的总位数。空间复杂度为 O(8) 时间，这是常数。

我们可以避免使用数组列表来存储给定数字的位。下面的程序展示了这一点。

文件名: MisMatchBits1.java

public class MisMatchingBits1
{

// a method that finds the number of mismatching bits
// in the numbers a and b
public int countMisMatchBit(int a, int b)
{
    // handling the base case
    // if both the numbers are the same, then 
    // the number of mismatching bits is zero.
    if(a == b)
    {
        return 0;
    }
    
    // for storing the count of the mismatching bits
    int countMisMatchBits = 0;
    
     // it is given in the problem that every number will 
     // fit in 8 bits. Hence, the loop runs till the eighth bit
     // Here, zero-indexing is used.
    for (int pos = 0; pos < 8; pos++) 
    {
 
        // right shifting both of the numbers by 'pos' and
        // checking whether the bit at the position pos is different
        // or not
        if (((a >> pos) & 1) != ((b >> pos) & 1)) 
        {
            countMisMatchBits = countMisMatchBits + 1;
        }
    }
    
    // return the count
    return countMisMatchBits;
}

// main method
public static void main(String[] argvs) 
{
    // creating an object of the class MisMatchingBits1
    MisMatchingBits1 obj = new MisMatchingBits1( );
    
    // the two input numbers
    int f1 = 9;
    int f2 = 15;
    
    int ans = obj.countMisMatchBit(f1, f2);
    System.out.println("The number of mismatching bits for the numbers " + f1 + " and " + f2 + " is: " + ans);
    System.out.println( );
    
    
    // the two input numbers
    f1 = 32;
    f2 = 31;
    
    ans = obj.countMisMatchBit(f1, f2);
    System.out.println("The number of mismatching bits for the numbers " + f1 + " and " + f2 + " is: " + ans);
    
    System.out.println( );
    
    
    // the two input numbers
    f1 = 40;
    f2 = 40;
    
    ans = obj.countMisMatchBit(f1, f2);
    System.out.println("The number of mismatching bits for the numbers " + f1 + " and " + f2 + " is: " + ans);
}
}

输出

The number of mismatching bits for the numbers 9 and 15 is: 2

The number of mismatching bits for the numbers 32 and 31 is: 6

The number of mismatching bits for the numbers 40 and 40 is: 0

复杂度分析: 程序只使用一个循环，该循环只运行 O(8) 次，这是常数。而且，程序不使用任何额外的空间。因此，程序的时间和空间复杂度均为 O(1)。

使用 XOR 运算符

找出不匹配位数的方法是使用按位 XOR。每当我们对两个数字应用按位 XOR 时，我们都会得到一个数字，其中那些位被设置为 1，表示这两个数字中的位不匹配。现在，计算 XOR 值中设置为 1 的位数。计算出的值就是我们的答案。让我们通过一个例子来理解这一点。

我们取两个数字，10 和 2。现在，10 ^ 2 = 8。这是因为 1010 ^ 0010 = 1000（值为 8）。我们看到，从右到左计算的第一个位设置为 1，因为数字 10 的第一个位是 1，而数字 2 的第一个位是 0（不匹配）。其余的其他位在两个数字中都匹配。因此，XOR 值中的其余位都是 0。

在 XOR 值中，我们看到只有一位设置为 1。因此，数字 10 和 2 的不匹配位数为 1。请看以下程序。

文件名: MismatchingBits2.java

public class MisMatchingBits2
{
// a method that finds the number of mismatching bits
// in the numbers a and b
public int countMisMatchBit(int a, int b)
{
    // handling the base case
    // if both the numbers are the same, then 
    // the number of mismatching bits is zero.
    if(a == b)
    {
        return 0;
    }
    
    // for storing the count of the mismatching bits
    int countMisMatchBits = 0;
    
     int xorVal = a ^ b;
     
     // loop that counts the number of set bits in the 
     // value xorVal
     while(xorVal != 0)
     {
         xorVal = xorVal & (xorVal - 1);
         countMisMatchBits = countMisMatchBits + 1;
     }
    
    // return the count
    return countMisMatchBits;
}

// main method
public static void main(String[] argvs) 
{
    // creating an object of the class MisMatchingBits2
    MisMatchingBits2 obj = new MisMatchingBits2( );
    
    // the two input numbers
    int f1 = 9;
    int f2 = 15;
    
    int ans = obj.countMisMatchBit(f1, f2);
    System.out.println("The number of mismatching bits for the numbers " + f1 + " and " + f2 + " is: " + ans);
    System.out.println( );
    
    
    // the two input numbers
    f1 = 32;
    f2 = 31;
    
    ans = obj.countMisMatchBit(f1, f2);
    System.out.println("The number of mismatching bits for the numbers " + f1 + " and " + f2 + " is: " + ans);
    
    System.out.println( );
    
    
    // the two input numbers
    f1 = 40;
    f2 = 40;
    
    ans = obj.countMisMatchBit(f1, f2);
    System.out.println("The number of mismatching bits for the numbers " + f1 + " and " + f2 + " is: " + ans);
}
}

输出

The number of mismatching bits for the numbers 9 and 15 is: 2

The number of mismatching bits for the numbers 32 and 31 is: 6

The number of mismatching bits for the numbers 40 and 40 is: 0

复杂度分析: 程序的时间和空间复杂度均为常数，即 O(1)。

注意：在本教程中，我们已经讨论了三个程序，并且从渐近的角度来看，所有程序的time complexity都是相同的。然而，在这三个程序中，第三个程序在复杂度方面是最好的。这是因为第三个程序中使用的 while 循环只运行 O(setBits) 次，其中 setBits 是两个给定数字的 XOR 值中设置为 1 的位数。通常，XOR 值中的设置为 1 的位数相对较少。因此，在大多数情况下，第三个程序的 while 循环的运行次数甚至会少于 O(8) 次。

下一主题Java 中的回文排列字符串

Java 中不匹配位的数量

简单方法

使用 XOR 运算符

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中不匹配位的数量

简单方法

使用 XOR 运算符

相关帖子

Java short Keyword

How to Improve Coding Skills in Java

NoSuchElementException

Scope Resolution Operator in Java

Java 中的静态数组

在 Java 中查找两个列表之间的差异

使用 Comparator 对 Java Vector 进行降序排序

Java 中交换首尾单词并反转中间字符

Java 中的欧几里得-穆林序列

Java 中一行交换两个变量

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器