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

Output

3

Categorized in:

Tagged in:

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