Number of Mismatching Bits in Java
In this Java tutorial, we'll be tackling the challenge of identifying the number of mismatched bits between two numbers (n1 and n2). Our goal is to calculate the number of different bits between the binary representations of both numbers, given that each number fits within 8 bits.
For instance:
Given the input of two numbers (n1 and n2), we first convert them into their binary representation. We then store their binary form in two separate array lists (one for n1 and one for n2). Afterward, using a loop, we can compare the bits between the two arrays and determine the number of mismatched bits.
Example 1:
Input: int n1 = 9, int n2 = 15 Output: The total number of mismatched bits is 2.
Explanation: The binary representation of 9 is 00001001 and the binary representation of 15 is 00001111. When comparing both binary forms, we see that the first five bits match while the sixth and seventh bits do not match. These two bits differ, with 0 for 9 and 1 for 15. Hence, there are two mismatched bits and the output is 2.
Example 2:
Input: int n1 = 32, int n2 = 31 Output: The total number of mismatched bits is 6.
Explanation: The binary representation of 32 is 00100000 and the binary representation of 31 is 00011111. When comparing both binary forms, we see that only the first two bits match. From the third bit onward, there is a mismatch until the eighth bit. The third bit for 32 is 1 and for 31 it is 0. The rest of the bits have a value of 0 for 32 and 1 for 31. Therefore, there are 6 mismatched bits and the output is 6.
Example 3:
Input: int n1 = 40, int n2 = 40 Output: The total number of mismatched bits is 0.
Explanation: Since both numbers are the same, their binary representation will also be the same. Hence, there will be no mismatched bits and the output is 0.
Simple Approach:
The simple approach to solving the problem of finding the number of mismatched bits between two numbers (n1 and n2) is as follows:
- Convert both numbers into their binary representation.
- Store their binary form in two separate array lists (one for n1 and one for n2).
- Use a loop to compare the bits between the two arrays and determine the number of mismatched bits.
This approach involves a straightforward process of converting the numbers into binary form, storing them in arrays, and comparing the bits between the arrays to find the number of mismatched bits.
Implementation 1:
File name – MisMatchedBits1.java
import java.util.ArrayList;
public class MisMatchedBits1
{
// A method to find the number of mismatched bits
// in the numbers x and y
public int countMismatchedBit(int x, int y)
{
// dealing with the base case
// if both the numbers are identical, then
// the number of mismatched bits = zero.
if(x == y)
{
return 0;
}
// to store the count of the mismatched bits
int countmmBits = 0;
// two lists that represent the binary representation in reverse order
// of the numbers x and y in 8 bits
ArrayList<Integer> list1 = new ArrayList<Integer>();
ArrayList<Integer> list2 = new ArrayList<Integer>();
// loop that converts the number x
// from decimal (base-10) to binary (base-2)
while(x != 0)
{
int n = x % 2;
x = x / 2;
list1.add(n);
}
// loop that converts the number y
// from decimal (base-10) to binary (base-2)
while(y != 0)
{
int n = y % 2;
y = y / 2;
list2.add(n);
}
// the lists size needs to be 8
// if the size of the lists is less than 8, it has
// to be increased upto 8 by adding 0 to it.
while(list1.size() != 8)
{
list1.add(0);
}
while(list2.size() != 8)
{
list2.add(0);
}
// loop for the comparison of bits of the numbers x and y
for(int i = 0; i < 8; i++)
{
if(list1.get(i) != list2.get(i))
{
// mismatch occurred. so, increase the count by 1
countmmBits = countmmBits + 1;
}
}
// return the count
return countmmBits;
}
// main method
public static void main(String[] argvs)
{
// creation of an object of the class MisMatchedBits1
MisMatchedBits1 obj = new MisMatchedBits1 ( );
// the two input numbers
int n1 = 11;
int n2 = 18;
int res = obj.countMismatchedBit(n1, n2);
System.out.println("The number of mismatching bits for the numbers " + n1 + " and " + n2 + " is: " + res);
System.out.println( );
// the two input numbers
n1 = 45;
n2 = 47;
res = obj.countMismatchedBit(n1, n2);
System.out.println("The number of mismatching bits for the numbers " + n1 + " and " + n2 + " is: " + res);
System.out.println( );
// the two input numbers
n1 = 68;
n2 = 68;
res = obj.countMismatchedBit(n1, n2);
System.out.println("The number of mismatching bits for the numbers " + n1 + " and " + n2 + " is: " + res);
}
}
Output:
Complexity Analysis:
Time Complexity: The time complexity of this approach is O(dig1 + dig2), where dig1 is the number of digits in f1 and dig2 is the number of digits in f2. This is because the first two while loops, which convert the numbers into binary form, take O(dig1) and O(dig2) time respectively. The other three loops (two while loops and one for loop) take constant time (O(8)) as they only run for a constant number of iterations.
Space Complexity: The space complexity of this approach is O(8), which is constant. This is because, regardless of the input size, the program only needs to store the binary representation of the two numbers in arrays of size 8 (assume every number fits in 8 bits).
Implementation 2:
The usage of array lists for storing the bits of the given number can be avoided.
The following program shows the same.
File name - MisMatchedBits2.java
public class MisMatchedBits2
{
// a method that finds the number of mismatching bits
// in the numbers x and y
public int countMisMatchBit(int x, int y)
{
// dealing with the base case
// if both the numbers are the same, then
// the number of mismatched bits = zero.
if(x == y)
{
return 0;
}
// to store the count of the mismatching bits
int countmmBits = 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 (((x >> pos) & 1) != ((y >> pos) & 1))
{
countmmBits = countmmBits + 1;
}
}
// return the count
return countmmBits;
}
// main method
public static void main(String[] argvs)
{
// creation of an object of the class MisMatchingBits2
MisMatchedBits2 obj = new MisMatchedBits2( );
// the two input numbers
int n1 = 11;
int n2 = 18;
int res = obj.countMisMatchBit(n1, n2);
System.out.println("The number of mismatching bits for the numbers " + n1 + " and " + n2 + " is: " + res);
System.out.println( );
// the two input numbers
n1 = 45;
n2 = 47;
res = obj.countMisMatchBit(n1, n2);
System.out.println("The number of mismatching bits for the numbers " + n1 + " and " + n2 + " is: " + res);
System.out.println( );
// the two input numbers
n1 = 68;
n2 = 68;
res = obj.countMisMatchBit(n1, n2);
System.out.println("The number of mismatching bits for the numbers " + n1 + " and " + n2 + " is: " + res);
}
} Output:
Complexity analysis:
Time Complexity: The time complexity of this program is O(8), where 8 is the number of bits required to represent a number in memory. This is because the for loop that runs from 0 to 7 takes constant time to execute, regardless of the size of the input numbers.
Space Complexity: The space complexity of this program is O (1), as it only requires a constant amount of memory to store variables used in the program, such as countMisMatchBits and pos.
Using XOR Operator
An alternate way to determine the number of bits that don't match is to utilize the bitwise XOR operation. By performing bitwise XOR on two numbers, a result is obtained whose set bits are only those that are not the same in both numbers. To get the answer, we calculate the number of set bits in the XOR result. Let's examine an example to understand this process.
Implementation 3:
File name - MisMatchingBits3
public class MisMatchingBits3
{
// a method to find the number of mismatching bits
// in the numbers x and y
public int countMisMatchBit(int x, int y)
{
// dealingnwith the base case
// if both the numbers are identical, then
// the number of mismatching bits = zero.
if(x == y)
{
return 0;
}
// to store the count of the mismatching bits
int countmmBits = 0;
int xorV = x ^ y;
// loop to count the number of set bits in the
// value xorV
while(xorV != 0)
{
xorV = xorV & (xorV - 1);
countmmBits = countmmBits + 1;
}
// return the count
return countmmBits;
}
// main method
public static void main(String[] argvs)
{
// creation of an object of the class MisMatchingBits3
MisMatchingBits3 obj = new MisMatchingBits3( );
// the two input numbers
int n1 = 11;
int n2 = 18;
int res = obj.countMisMatchBit(n1, n2);
System.out.println("The number of mismatching bits for the numbers " + n1 + " and " + n2 + " is: " + res);
System.out.println( );
// the two input numbers
n1 = 45;
n2 = 47;
res = obj.countMisMatchBit(n1, n2);
System.out.println("The number of mismatching bits for the numbers " + n1 + " and " + n2 + " is: " + res);
System.out.println( );
// the two input numbers
n1 = 68;
n2 = 68;
res = obj.countMisMatchBit(n1, n2);
System.out.println("The number of mismatching bits for the numbers " + n1 + " and " + n2 + " is: " + res);
}
}
Output:
Complexity Analysis:
Time Complexity - The time complexity of the above program is O (1) because the program only performs a constant number of operations, regardless of the size of the input numbers.
Space Complexity - The space complexity is also O (1) because the program only requires a constant amount of memory to store a few variables.