极客教程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)次。