How to Count number of bits to be flipped to convert A to B ?

  • Write the program to count number of bits needed to be flipped to convert ‘a’ to ‘b’. For Example given two numbers a = 6 and b = 12; then the output is 2
    • Binary representation of a is 00000110
    • Binary representation of b is 00001100
    • We need to flip highlighted two bits in a
    • To make it b.

Explanation

  • Calculate XOR of A and B.
a_xor_b = A ^ B
  • Count the set bits in the above Calculated XOR result.
CountSetBits(a_xor_b)

Sample Code in C#

/ Count number of bits to be 
// flipped to convert A into B
using System;

public class Count {

// Function that count set bits
public static int countSetBits(int n)
{
int count = 0;
while (n != 0) {
count += n & 1;
n >>= 1;
}
return count;
}

// Function that return
// count of flipped number
public static int FlippedCount(int a, int b)
{
// Return count of set
// bits in a XOR b
return countSetBits(a ^ b);
}

// Driver code
public static void Main()
{
int a = 17;
int b = 55;
Console.WriteLine(FlippedCount(a, b));
}
}

// This code is contributed by vt_m.

Output

3

Categorized in:

Tagged in:

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,