Last Updated: 2 Dec, 2020
Number of Mismatching Bits
Easy
Asked in companies
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
Approaches
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
- 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.
- If it doesn't match then increment the “count” by 1.
- Return the “count”.
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.
- Increment the “count” by 1.
- Update “xorValue” as xorValue = (xorValue & (xorValue - 1)). This step unset the rightmost bit in “xorValue”.
- Return the “count”.