Java中的不匹配位数

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

例1 :

输入

int f1 = 9

int f2 = 15

输出

不匹配的比特总数为2。

解释。

数字9的8位二进制表示是00001001，数字15的8位二进制表示是00001111。如果我们从左到右比较这两个二进制表示法，我们发现前五位是匹配的。第六位和第七位不匹配，因为数字9的位数都是0，数字15的位数都是1。因此，有两个位不匹配。因此，输出为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 list1 = new ArrayList();
    ArrayList list2 = new ArrayList();

    // 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-loop需要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时，我们会得到一个数字，其被设置的那些位在这两个数字中不匹配。现在，计算一下XOR值中被设置的位数。这个计算值就是我们的答案。让我们举个例子来理解这个问题。

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

在XOR值中，我们看到只有一个位被设置。因此，数字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)。

注意：我们在本教程中讨论了三个程序，渐进地看，所有程序的时间复杂性都是一样的。然而，在所有这三个程序中，第三个程序的复杂性是最好的。这是因为第三个程序中使用的while-loop只运行O( setBits ) 次，其中 setBits 是两个给定数字的XOR值中的set位数。通常情况下，在一个XOR值中，设置位的数量是相当少的。因此，在大多数情况下，第三个程序的while-loop的运行次数甚至少于O(8)次。