Last Updated: 21 Nov, 2021

Number of Flips

Easy

Asked in companies

Solve now

Problem statement

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

Solve now

Approaches

01 Approach

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’.

Solve now

02 Approach

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.

Algorithm:

Set ‘C’ as ‘A’ XOR ‘B’.
Declare ‘ANS’ to store the number of set bits of ‘C’.
Set ‘ANS’ as 0.
While ‘C’ >0, do the following:
- If ‘C’ % 2 == 1:
  - Set ‘ANS’ as ‘ANS’+1.
- Set ‘C’ as ‘C’/2.
Return ‘ANS’.

Solve now