Number of Mismatching Bits
Given two integers "first" and "second". Find the number of bits that do not match in the binary representation of the given numbers.

For example, let "first" be 11 and "second" be 15. Writing both the given numbers in binary we get first = 1011(binary representation of 11) and second = 1111(binary representation of 15) we can see all the bits are the same except the second bit.

Therefore only 1 bit differs hence we return 1 as shown in the diagram.

Note:

1. Do not print anything, just implement the provided function and return the number of mismatching bits for the given numbers.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. The next ‘T’ lines represent the ‘T’ test cases. The only line of each test case contains 2 space-separated integers "first" and "second"

Output Format

For each test case, print a single integer denoting the number of mismatched bits in their binary representation. The output of each test case will be printed in a separate line.

Constraints:

1

Question

Number of Mismatching Bits

Given two integers "first" and "second". Find the number of bits that do not match in the binary representation of the given numbers.

For example, let "first" be 11 and "second" be 15. Writing both the given numbers in binary we get first = 1011(binary representation of 11) and second = 1111(binary representation of 15) we can see all the bits are the same except the second bit.

Therefore only 1 bit differs hence we return 1 as shown in the diagram.

Note:

1. Do not print anything, just implement the provided function and return the number of mismatching bits for the given numbers.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.
The only line of each test case contains 2 space-separated integers "first" and "second"

Output Format

For each test case, print a single integer denoting the number of mismatched bits in their binary representation.

The output of each test case will be printed in a separate line.

Constraints:

1 <= T <= 10 ^ 5
0 <= first, second <= 10^9

Where ‘T’ is the total number of test cases and "first", " second" are the given numbers.

Time limit: 1 second

Accepted Answer

Step 1 : I used bitwise shift operators here. I first ran a loop for 'i' from 0 to 32 (as 32 bits is maximum)
Step 2 : Then right shifted the bits of both numbers by 'i' places.
Step 3 : Checked whether the bit at 0th position is different, if yes then increase the counter variable.
Step 4 : Using bitwise AND by 1 for both numbers to get the 1st bit.
Step 5 : Displayed the count.

Accepted Answer

Brute force Approach

The key idea is to check for each bit if it is different or not.

Consider the following steps:

Create a variable “count” which stores the count of mismatched bits. Initialize it to zero.
Create a loop using a variable ‘i’ such that 0 <= ‘i’ < 30 since 2^30 > 10^9
1. Right shift the “first” and “second” ‘i’ times and check if the last bit is matching or not. We can easily do this by taking AND with 1 and then comparing.
2. If it doesn't match then increment the “count” by 1.
Return the “count”.

Space Complexity: O(1)Explanation:

O(1).

We are using constant space

Time Complexity: O(1)Explanation:

O(1)

In each case, we perform 30 operations which is a constant hence it takes constant time.

Java (SE 1.8)

/*

    Time Complexity: O(1)

    Space Complexity: O(1)



*/







public class Solution 

{



	public static int numberOfMismatchingBits(int first, int second)

	{

		//	To store the count of mismatched bits.

		int count = 0;



		//	Since, the numbers are less than 2^30 run the loop from '0' to '29' only

		for (int i = 0; i < 30; i++)

		{

			//	Right shift both the numbers by 'i' and check if the bit at the 0th position is different

			if (((first >> i) & 1) != ((second >> i) & 1))

			{

				count = count + 1;

			}

		}



		return count;

	}



}

Python (3.5)

'''

    Time Complexity: O(1)

    Space Complexity: O(1)



'''



def numberOfMismatchingBits(first, second):



    #  To store the count of mismatched bits.

    count = 0



    #  Since, the numbers are less than 2^30 run the loop from '0' to '29' only

    for i in range(30):

        

        #  Right shift both the numbers by 'i' and check if the bit at the 0th position is different

        if (((first >> i) & 1) != ((second >> i) & 1)):

            count = count + 1

        

    return count

C++ (g++ 5.4)

/*
    Time Complexity: O(1)
    Space Complexity: O(1)

*/

int numberOfMismatchingBits(int first, int second)
{
	//	To store the count of mismatched bits.
	int count = 0;

	//	Since, the numbers are less than 2^30 run the loop from '0' to '29' only
	for (int i = 0; i < 30; i++)
	{
		//	Right shift both the numbers by 'i' and check if the bit at the 0th position is different
		if (((first >> i) & 1) != ((second >> i) & 1))
		{
			count = count + 1;
		}
	}

	return count;
}

Accepted Answer

XOR approach

Since we need to find the number of mismatching bits, we can use the XOR operator as the XOR of two given numbers will give the result 1 in the bits where the bits of the given numbers differ as shown in the truth table above.

Once the result is calculated, we just need to count the number of set bits in the answer.

To calculate the number of set bits we can either use a library function (for eg __builtin_popcount in C++) or calculate it using a loop.

Consider the following steps:

Take the XOR of the given two numbers and store it in a variable “xorValue”.
Count the number of set bits in the “xorValue”. Create a variable “count” and initialize it to 0 which stores the number of set bits.
Create a loop that counts the number of set bits in “xorValue”. Loop until “xorValue” is greater than 0.
1. Increment the “count” by 1.
2. Update “xorValue” as xorValue = (xorValue & (xorValue - 1)). This step unset the rightmost bit in “xorValue”.
Return the “count”.

Space Complexity: O(1)Explanation:

O(1)

We are using constant space.

Time Complexity: O(1)Explanation:

O(1)

In each case, we will loop for O(No. of set bits) which will be O(30) in the worst-case according to given constraints. Since 30 is a constant we need constant time.

Java (SE 1.8)

/*

    Time Complexity: O(1)

    Space Complexity: O(1)



*/





public class Solution 

{



	public static int numberOfMismatchingBits(int first, int second)

	{

		//	Get the XOR of the given two integers.

		int xorValue = first ^ second;



		//	To store the count of set bits.

		int count = 0;



		while (xorValue > 0)

		{

			count = count + 1;



			//	Unset the right-most set bit.

			xorValue = ((xorValue - 1) & xorValue);

		}



		return count;

	}



}

Python (3.5)

'''

    Time Complexity: O(1)

    Space Complexity: O(1)



'''



def numberOfMismatchingBits(first, second):



    #  Get the XOR of the given two integers.

    xorValue = first ^ second



    #  To store the count of set bits.

    count = 0



    while (xorValue > 0):

        count = count + 1



        #  Unset the right-most set bit.

        xorValue = ((xorValue - 1) & xorValue)



    return count

C++ (g++ 5.4)

/*
    Time Complexity: O(1)
    Space Complexity: O(1)

*/

int numberOfMismatchingBits(int first, int second)
{
	//	Get the XOR of the given two integers.
	int xorValue = first ^ second;

	//	To store the count of set bits.
	int count = 0;

	while (xorValue > 0)
	{
		count = count + 1;

		//	Unset the right-most set bit.
		xorValue = ((xorValue - 1) & xorValue);
	}

	return count;
}

Given two integers "first" and "second". Find the number of bits that do not match in the binary representation of the given numbers.

For example, let "first" be 11 and "second" be 15. Writing both the given numbers in binary we get first = 1011(binary representation of 11) and second = 1111(binary representation of 15) we can see all the bits are the same except the second bit.

Therefore only 1 bit differs hence we return 1 as shown in the diagram.

Note:

Input format:

Output Format

Constraints:

Top Wells Fargo Intern interview questions & answers

Popular interview questions of Intern

Top HR questions asked in Wells Fargo Intern