Number of Flips
Ninja is learning the binary representation of the numbers. He wanted to practice the topic, so he picked a question. The problem statement says, two numbers, ‘A’ and ‘B’ are given. Find the number of bits of ‘B’ that should be flipped to convert it into ‘A’.Can you help Ninja to solve this problem?

You are given two integers, ‘A’ and ‘B’.Find the number of bits of ‘B’ that should be flipped to convert it into ‘A’.

For Example

If ‘A’ is 13(1101) and ‘B’ is 7(0111), The number of bits that should be flipped is 2(0111).

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases. The first line of each test case contains two integers, ‘A’ and ‘B’.

Output Format:

For each test case, print ‘an integer corresponding to the minimum number of swaps required. Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1

Question

Number of Flips

Ninja is learning the binary representation of the numbers. He wanted to practice the topic, so he picked a question. The problem statement says, two numbers, ‘A’ and ‘B’ are given. Find the number of bits of ‘B’ that should be flipped to convert it into ‘A’.Can you help Ninja to solve this problem?

You are given two integers, ‘A’ and ‘B’.Find the number of bits of ‘B’ that should be flipped to convert it into ‘A’.

For Example

If ‘A’ is 13(1101) and ‘B’ is 7(0111), The number of bits that should be flipped is 2(0111).

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains two integers, ‘A’ and ‘B’.

Output Format:

For each test case, print ‘an integer corresponding to the minimum number of swaps required.

Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= ‘A’,’B’ <= 10^9.

Time limit: 1 sec

Accepted Answer

For this question, it can be observed that there can be only two possible solutions for an alternate binary string. The resultant string will look like either of the two cases:

1. 010101…
2. 101010…
3.
Now, in order to find the minimum replacements, count the number of replacements to convert the string in type 1 and store it in variable count.
For type2, the number of replacements will be n-count (n is length of string).
So, the answer will be min(count, n-count).
To calculate the number of replacements for type 1, traverse the string and loop from i=0 to len-1. If 1 is present at even index positions or 0 is present at odd index positions, then we need to flip the bit, so update the count every time. The count after traversing the entire string will be the number of replacements required to convert the string to type 1.
Time Complexity : O(N)
Auxiliary Space : O(1)

Accepted Answer

Brute Force.

In this approach, we will simply iterate through all the bits of ‘A’ and ‘B’ and count the number of bits that are not matching, as if we just change these mismatched bits, we will find the number of bits that should be flipped.

At last, we will return ‘ANS’ storing the number of flips required.

Algorithm:

Declare ‘ANS’ to store the required answer.
While ‘A’ is greater than 0 or ‘B’ is greater than 0:
- Set bit_A as A%2.
- Set bit_B as B%2.
- If bit_A is not equal to bit_B:
  - Mismatched bit found.
  - Increase ‘ANS’ as ‘ANS’+1.
- Set ‘A’ as ‘A’/2.
- Set ‘B’ as ‘B’/2.
Return ‘ANS’.

Space Complexity: O(1)Explanation:

O(1).

In this approach, we are using constant space. Hence, the overall space complexity is O(1).

Time Complexity: O(logn)Explanation:

O(log(maximum of A and B)), where ‘A’ and ‘B’ are the given numbers.

In this approach, we traverse all the bits of ‘A’ and ‘B’.The number of bits of ‘A’ is of the order O(log(A)). Hence, the overall time complexity is O(log(maximum of A and B)).

Java (SE 1.8)


/*
    Time Complexity: O( log(maximum of A and B) ) 
    Space Complexity: O(1)

    where A and B are the given numbers.
*/

public class Solution {

	public static int numberOfFlips(int a, int b) {
	 
		  // ans will store the number of bits to be flipped.
	    int ans = 0;

	    while (a > 0 || b > 0){

	        int bitA = a % 2;
	        int bitB = b % 2;
	        if (bitA != bitB){
	            // Mismatched bit found.
	            ans = ans + 1;
	        }
	        a = a / 2;
	        b = b / 2;
	    }

	    return ans;
	}

}

C++ (g++ 5.4)

/*
    Time Complexity: O( log(maximum of A and B) ) 
    Space Complexity: O(1)

    where ‘A’ and ‘B’ are the given numbers.
*/

int numberOfFlips(int a, int b)
{
    // ans will store the number of bits to be flipped.
    int ans = 0;

    while (a > 0 or b > 0){

        int bitA = a % 2;
        int bitB = b % 2;
        if (bitA != bitB){
            // Mismatched bit found.
            ans = ans + 1;
        }
        a = a / 2;
        b = b / 2;
    }

    return ans;

}

Python (3.5)

"""

    Time Complexity: O( log(maximum of A and B) ) 

    Space Complexity: O(1)



    where ‘A’ and ‘B’ are the given numbers.

"""





from typing import *





def numberOfFlips(a: int, b: int) -> int:



    # ans will store the number of bits to be flipped.

    ans = 0



    while a > 0 or b > 0:



        bitA = a % 2

        bitB = b % 2

        if bitA != bitB:

            # Mismatched bit found.

            ans = ans + 1

        a = a // 2

        b = b // 2



    return ans

Accepted Answer

Using bitwise XOR.

In this approach, we will first take the bitwise XOR of ‘A’ and ‘B’ in a variable ‘C’.Now, the ‘C’ will contain only those bit sets that are mismatching in ‘A’ and ‘B’ for the following property of XOR:

0 XOR 0 is 0.

0 XOR 1 is 1.

1 XOR 0 is 1.

1 XOR 1 is 0.

We will simply count the number of set bits in ‘C’ and return the required number.