Last Updated: 22 Feb, 2021
Conversion
Easy
Asked in companies
You are given two integers, ‘N’ and ‘M’. You are supposed to perform the following operation to convert ‘N’ to ‘M’.
In one operation, you can:
1. Choose any bit in ‘N’.
2. Flip the chosen bit, i.e., if the bit is ‘0’, make it ‘1’ and vice versa.
You are supposed to find the minimum number of operations needed to convert ‘N’ to ‘M’.
Input Format:
The first line of input contains an integer 'T’, denoting the number of test cases. The test cases follow.
The first line of each test case contains two integers, ‘N’ and ‘M’.
Output Format:
Print the minimum number of operations needed to convert from ‘N’ to ‘M’.
Print the output of each test case in a new line.
Constraints:
1<= T <= 10^4
0 <= N, M <= 10^9
Where ’T’ is the number of test cases and ‘N’,’M’ are the given integers.
Time Limit: 1 sec
Approaches
The idea is to iterate through each bit of the two numbers, and if at any position the bits of N and M are different, we will flip that bit in N.
- Define a variable count and initialize it to 0. We will use this variable to count the number of bits we need to flip to make N equal to M.
- Iterate through each bit of N and M,
- Check if the current bit is the same in N and M or not.
- If the bits are different, increment count by 1.
- Check if the current bit is the same in N and M or not.
- Return count.
The idea is to take the xor of both the numbers and then count the number of set bits in the xor of N and M. The number of bits in the XOR of both the given numbers will be equal to the number of bits that are different in N and M.
The steps are as follows:
- Initialize K to N(XOR)M and count to 0. We will use the count variable to count the number of set bits in K.
- While K is not zero, do the following steps:
- Do bitwise and of K and K - 1 and assign this value to ‘K’. Doing the bitwise and of K and K-1 unsets the rightmost bit in K.
- Increment count by 1.
In this process, we unset the rightmost set bit at once. The number of times this loop will run will be equal to the number of set bits.