Posted on by Kalkicode
Code Bit Logic

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

The given problem is to find the minimum number of bits that need to be flipped in order to convert one integer 'A' to another integer 'B'. In other words, we want to determine how many bit positions differ between the two numbers. The problem can be solved using bitwise operations efficiently.

Explanation with Suitable Example

Let's take an example to understand the problem better. Consider two integers 'A' and 'B' with their binary representations as follows:

    A = 43 (Binary: 101011)
    B = 25 (Binary: 011001)

To convert A to B, we need to flip three bits:

  1. Bit at position 1 (from the right) needs to be flipped from 1 to 0.
  2. Bit at position 3 needs to be flipped from 1 to 0.
  3. Bit at position 5 needs to be flipped from 0 to 1.

Standard Pseudocode and Algorithm

// Function to count the number of bits to be flipped to convert A to B
flippedCount(a, b):
    // Perform bitwise XOR between 'a' and 'b' and store the result in 'num'
    num = a XOR b
    // Initialize 'count' to 0 to track the number of bit flips required
    count = 0

    // Count the number of set bits (1s) in 'num' using Brian Kernighan's algorithm
    while num is not 0:
        // Increment 'count' by 1
        count = count + 1
        // Turn off the rightmost set bit in 'num' using 'num = num & (num - 1)'
        num = num AND (num - 1)

    // Display the number of bit flips required (stored in 'count')
    print("Output:", count)

The code provided in the question already implements an efficient algorithm using bitwise operations to find the number of bit flips required. Here's the standard pseudocode for the algorithm:

  1. Define a function named 'flippedCount' that takes two integer inputs 'a' and 'b'.
  2. Within the function, perform a bitwise XOR operation between 'a' and 'b' and store the result in a variable called 'num'.
  3. Initialize a variable called 'count' to 0 to keep track of the number of bit flips required.
  4. Use a while loop to count the number of set bits (1s) in 'num' using the Brian Kernighan's algorithm: a. Increment 'count' by 1. b. Perform 'num = num & (num - 1)' to turn off the rightmost set bit in 'num'. c. Repeat steps 'a' and 'b' until 'num' becomes 0.
  5. Display the value of 'count', which represents the number of bit flips required to convert 'A' to 'B'.

The algorithm uses the property of XOR that sets a bit if it differs between the two numbers. The Brian Kernighan's algorithm helps efficiently count the set bits in the XOR result.

Code Solution

// C program 
// Count number of bits to be flipped to convert A to B
#include <stdio.h>

// Calculate how many bit changes are required to make equal numbers
void flippedCount(int a, int b)
{
	// Display given number
	printf("\n Given number ( a : %d, b : %d) ", a, b);
	int num = (a ^ b);
	int count = 0;
	// Count number of active bits
	while (num > 0)
	{
		count++;
		num = num & (num - 1);
	}
	// Display calculated result 
	printf("\n Output : %d", (count));
}
int main(int argc, char
	const *argv[])
{
	int a = 43;
	int b = 25;
	// a = 43    (1 0 1 0 1 1)
	// b = 25    (0 1 1 0 0 1) 
	//            ↓ ↓ ↓ ↓ ↓ ↓
	//           (1 1 0 0 1 0)
	// Bit changes = 3
	flippedCount(a, b);
	// Case 2
	a = 12;
	b = 4;
	// a = 12    (1 1 0 0)
	// b = 4     (0 1 0 0) 
	//            ↓ ↓ ↓ ↓ 
	//           (1 0 0 0 )
	// Bit changes =  1
	flippedCount(a, b);
	// Case 3
	a = 7;
	b = 7;
	// a = 7     (1 1 1 )
	// b = 7     (1 1 1 )
	//            ↓ ↓ ↓ 
	//           (0 0 0 )
	// Bit changes =  0
	flippedCount(a, b);
	return 0;
}

Output

 Given number ( a : 43, b : 25)
 Output : 3
 Given number ( a : 12, b : 4)
 Output : 1
 Given number ( a : 7, b : 7)
 Output : 0
/*
  Java program
  Count number of bits to be flipped to convert A to B
*/
public class BitManipulation
{
    // Calculate how many bit changes are required to make equal numbers
    public void flippedCount(int a, int b)
    {
        // Display given number
        System.out.print("\n Given number ( a : " + a + ", b : " + b + ") ");
        int num = (a ^ b);
        int count = 0;
        // Count number of active bits
        while (num > 0)
        {
            count++;
            num = num & (num - 1);
        }
        // Display calculated result 
        System.out.print("\n Output : " + (count) );
    }

    public static void main(String[] args)
    {
        BitManipulation task = new BitManipulation();
        int a = 43;
        int b = 25;
        // a = 43    (1 0 1 0 1 1)
        // b = 25    (0 1 1 0 0 1) 
        //            ↓ ↓ ↓ ↓ ↓ ↓
        //           (1 1 0 0 1 0)
        // Bit changes = 3
        task.flippedCount(a, b);
        // Case 2
        a = 12;
        b = 4;
        // a = 12    (1 1 0 0)
        // b = 4     (0 1 0 0) 
        //            ↓ ↓ ↓ ↓ 
        //           (1 0 0 0 )
        // Bit changes =  1
        task.flippedCount(a, b);
        // Case 3
        a = 7;
        b = 7;
        // a = 7     (1 1 1 )
        // b = 7     (1 1 1 )
        //            ↓ ↓ ↓ 
        //           (0 0 0 )
        // Bit changes =  0
        task.flippedCount(a, b);
    }
}

Output

 Given number ( a : 43, b : 25)
 Output : 3
 Given number ( a : 12, b : 4)
 Output : 1
 Given number ( a : 7, b : 7)
 Output : 0
// Include header file
#include <iostream>

using namespace std;
/*
  C++ program
  Count number of bits to be flipped to convert A to B
*/
class BitManipulation
{
	public:
		// Calculate how many bit changes are required to make equal numbers
		void flippedCount(int a, int b)
		{
			// Display given number
			cout << "\n Given number ( a : " << a << ", b : " << b << ") ";
			int num = (a ^ b);
			int count = 0;
			// Count number of active bits
			while (num > 0)
			{
				count++;
				num = num &(num - 1);
			}
			// Display calculated result
			cout << "\n Output : " << (count);
		}
};
int main()
{
	BitManipulation task = BitManipulation();
	int a = 43;
	int b = 25;
	// a = 43    (1 0 1 0 1 1)
	// b = 25    (0 1 1 0 0 1)
	//            ↓ ↓ ↓ ↓ ↓ ↓
	//           (1 1 0 0 1 0)
	// Bit changes = 3
	task.flippedCount(a, b);
	// Case 2
	a = 12;
	b = 4;
	// a = 12    (1 1 0 0)
	// b = 4     (0 1 0 0)
	//            ↓ ↓ ↓ ↓
	//           (1 0 0 0 )
	// Bit changes =  1
	task.flippedCount(a, b);
	// Case 3
	a = 7;
	b = 7;
	// a = 7     (1 1 1 )
	// b = 7     (1 1 1 )
	//            ↓ ↓ ↓
	//           (0 0 0 )
	// Bit changes =  0
	task.flippedCount(a, b);
	return 0;
}

Output

 Given number ( a : 43, b : 25)
 Output : 3
 Given number ( a : 12, b : 4)
 Output : 1
 Given number ( a : 7, b : 7)
 Output : 0
<?php
/*
  Php program
  Count number of bits to be flipped to convert A to B
*/
class BitManipulation
{
	// Calculate how many bit changes are required to make equal numbers
	public	function flippedCount($a, $b)
	{
		// Display given number
		echo "\n Given number ( a : ". $a .", b : ". $b .") ";
		$num = ($a ^ $b);
		$count = 0;
		// Count number of active bits
		while ($num > 0)
		{
			$count++;
			$num = $num & ($num - 1);
		}
		// Display calculated result
		echo "\n Output : ". ($count);
	}
}

function main()
{
	$task = new BitManipulation();
	$a = 43;
	$b = 25;
	// a = 43    (1 0 1 0 1 1)
	// b = 25    (0 1 1 0 0 1)
	//            ↓ ↓ ↓ ↓ ↓ ↓
	//           (1 1 0 0 1 0)
	// Bit changes = 3
	$task->flippedCount($a, $b);
	// Case 2
	$a = 12;
	$b = 4;
	// a = 12    (1 1 0 0)
	// b = 4     (0 1 0 0)
	//            ↓ ↓ ↓ ↓
	//           (1 0 0 0 )
	// Bit changes =  1
	$task->flippedCount($a, $b);
	// Case 3
	$a = 7;
	$b = 7;
	// a = 7     (1 1 1 )
	// b = 7     (1 1 1 )
	//            ↓ ↓ ↓
	//           (0 0 0 )
	// Bit changes =  0
	$task->flippedCount($a, $b);
}
main();

Output

 Given number ( a : 43, b : 25)
 Output : 3
 Given number ( a : 12, b : 4)
 Output : 1
 Given number ( a : 7, b : 7)
 Output : 0
// Include namespace system
using System;
/*
  C# program
  Count number of bits to be flipped to convert A to B
*/
public class BitManipulation
{
	// Calculate how many bit changes are required to make equal numbers
	public void flippedCount(int a, int b)
	{
		// Display given number
		Console.Write("\n Given number ( a : " + a + ", b : " + b + ") ");
		int num = (a ^ b);
		int count = 0;
		// Count number of active bits
		while (num > 0)
		{
			count++;
			num = num & (num - 1);
		}
		// Display calculated result
		Console.Write("\n Output : " + (count));
	}
	public static void Main(String[] args)
	{
		BitManipulation task = new BitManipulation();
		int a = 43;
		int b = 25;
		// a = 43    (1 0 1 0 1 1)
		// b = 25    (0 1 1 0 0 1)
		//            ↓ ↓ ↓ ↓ ↓ ↓
		//           (1 1 0 0 1 0)
		// Bit changes = 3
		task.flippedCount(a, b);
		// Case 2
		a = 12;
		b = 4;
		// a = 12    (1 1 0 0)
		// b = 4     (0 1 0 0)
		//            ↓ ↓ ↓ ↓
		//           (1 0 0 0 )
		// Bit changes =  1
		task.flippedCount(a, b);
		// Case 3
		a = 7;
		b = 7;
		// a = 7     (1 1 1 )
		// b = 7     (1 1 1 )
		//            ↓ ↓ ↓
		//           (0 0 0 )
		// Bit changes =  0
		task.flippedCount(a, b);
	}
}

Output

 Given number ( a : 43, b : 25)
 Output : 3
 Given number ( a : 12, b : 4)
 Output : 1
 Given number ( a : 7, b : 7)
 Output : 0
/*
  Node Js program
  Count number of bits to be flipped to convert A to B
*/
class BitManipulation
{
	// Calculate how many bit changes are required to make equal numbers
	flippedCount(a, b)
	{
		// Display given number
		process.stdout.write("\n Given number ( a : " + a + ", b : " + b + ") ");
		var num = (a ^ b);
		var count = 0;
		// Count number of active bits
		while (num > 0)
		{
			count++;
			num = num & (num - 1);
		}
		// Display calculated result
		process.stdout.write("\n Output : " + (count));
	}
}

function main()
{
	var task = new BitManipulation();
	var a = 43;
	var b = 25;
	// a = 43    (1 0 1 0 1 1)
	// b = 25    (0 1 1 0 0 1)
	//            ↓ ↓ ↓ ↓ ↓ ↓
	//           (1 1 0 0 1 0)
	// Bit changes = 3
	task.flippedCount(a, b);
	// Case 2
	a = 12;
	b = 4;
	// a = 12    (1 1 0 0)
	// b = 4     (0 1 0 0)
	//            ↓ ↓ ↓ ↓
	//           (1 0 0 0 )
	// Bit changes =  1
	task.flippedCount(a, b);
	// Case 3
	a = 7;
	b = 7;
	// a = 7     (1 1 1 )
	// b = 7     (1 1 1 )
	//            ↓ ↓ ↓
	//           (0 0 0 )
	// Bit changes =  0
	task.flippedCount(a, b);
}
main();

Output

 Given number ( a : 43, b : 25)
 Output : 3
 Given number ( a : 12, b : 4)
 Output : 1
 Given number ( a : 7, b : 7)
 Output : 0
#   Python 3 program
#   Count number of bits to be flipped to convert A to B

class BitManipulation :
	#  Calculate how many bit changes are required to make equal numbers
	def flippedCount(self, a, b) :
		#  Display given number
		print("\n Given number ( a : ", a ,", b : ", b ,") ", end = "")
		num = (a ^ b)
		count = 0
		#  Count number of active bits
		while (num > 0) :
			count += 1
			num = num & (num - 1)
		
		#  Display calculated result 
		print("\n Output : ", (count), end = "")
	

def main() :
	task = BitManipulation()
	a = 43
	b = 25
	#  a = 43    (1 0 1 0 1 1)
	#  b = 25    (0 1 1 0 0 1) 
	#             ↓ ↓ ↓ ↓ ↓ ↓
	#            (1 1 0 0 1 0)
	#  Bit changes = 3
	task.flippedCount(a, b)
	#  Case 2
	a = 12
	b = 4
	#  a = 12    (1 1 0 0)
	#  b = 4     (0 1 0 0) 
	#             ↓ ↓ ↓ ↓ 
	#            (1 0 0 0 )
	#  Bit changes =  1
	task.flippedCount(a, b)
	#  Case 3
	a = 7
	b = 7
	#  a = 7     (1 1 1 )
	#  b = 7     (1 1 1 )
	#             ↓ ↓ ↓ 
	#            (0 0 0 )
	#  Bit changes =  0
	task.flippedCount(a, b)

if __name__ == "__main__": main()

Output

 Given number ( a :  43 , b :  25 )
 Output :  3
 Given number ( a :  12 , b :  4 )
 Output :  1
 Given number ( a :  7 , b :  7 )
 Output :  0
#   Ruby program
#   Count number of bits to be flipped to convert A to B

class BitManipulation 
	#  Calculate how many bit changes are required to make equal numbers
	def flippedCount(a, b) 
		#  Display given number
		print("\n Given number ( a : ", a ,", b : ", b ,") ")
		num = (a ^ b)
		count = 0
		#  Count number of active bits
		while (num > 0) 
			count += 1
			num = num & (num - 1)
		end

		#  Display calculated result 
		print("\n Output : ", (count))
	end

end

def main() 
	task = BitManipulation.new()
	a = 43
	b = 25
	#  a = 43    (1 0 1 0 1 1)
	#  b = 25    (0 1 1 0 0 1) 
	#             ↓ ↓ ↓ ↓ ↓ ↓
	#            (1 1 0 0 1 0)
	#  Bit changes = 3
	task.flippedCount(a, b)
	#  Case 2
	a = 12
	b = 4
	#  a = 12    (1 1 0 0)
	#  b = 4     (0 1 0 0) 
	#             ↓ ↓ ↓ ↓ 
	#            (1 0 0 0 )
	#  Bit changes =  1
	task.flippedCount(a, b)
	#  Case 3
	a = 7
	b = 7
	#  a = 7     (1 1 1 )
	#  b = 7     (1 1 1 )
	#             ↓ ↓ ↓ 
	#            (0 0 0 )
	#  Bit changes =  0
	task.flippedCount(a, b)
end

main()

Output

 Given number ( a : 43, b : 25) 
 Output : 3
 Given number ( a : 12, b : 4) 
 Output : 1
 Given number ( a : 7, b : 7) 
 Output : 0
/*
  Scala program
  Count number of bits to be flipped to convert A to B
*/
class BitManipulation
{
	// Calculate how many bit changes are required to make equal numbers
	def flippedCount(a: Int, b: Int): Unit = {
		// Display given number
		print("\n Given number ( a : " + a + ", b : " + b + ") ");
		var num: Int = (a ^ b);
		var count: Int = 0;
		// Count number of active bits
		while (num > 0)
		{
			count += 1;
			num = num & (num - 1);
		}
		// Display calculated result
		print("\n Output : " + (count));
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: BitManipulation = new BitManipulation();
		var a: Int = 43;
		var b: Int = 25;
		// a = 43    (1 0 1 0 1 1)
		// b = 25    (0 1 1 0 0 1)
		//            ↓ ↓ ↓ ↓ ↓ ↓
		//           (1 1 0 0 1 0)
		// Bit changes = 3
		task.flippedCount(a, b);
		// Case 2
		a = 12;
		b = 4;
		// a = 12    (1 1 0 0)
		// b = 4     (0 1 0 0)
		//            ↓ ↓ ↓ ↓
		//           (1 0 0 0 )
		// Bit changes =  1
		task.flippedCount(a, b);
		// Case 3
		a = 7;
		b = 7;
		// a = 7     (1 1 1 )
		// b = 7     (1 1 1 )
		//            ↓ ↓ ↓
		//           (0 0 0 )
		// Bit changes =  0
		task.flippedCount(a, b);
	}
}

Output

 Given number ( a : 43, b : 25)
 Output : 3
 Given number ( a : 12, b : 4)
 Output : 1
 Given number ( a : 7, b : 7)
 Output : 0
/*
  Swift 4 program
  Count number of bits to be flipped to convert A to B
*/
class BitManipulation
{
	// Calculate how many bit changes are required to make equal numbers
	func flippedCount(_ a: Int, _ b: Int)
	{
		// Display given number
		print("\n Given number ( a : ", a ,", b : ", b ,") ", terminator: "");
		var num: Int = (a ^ b);
		var count: Int = 0;
		// Count number of active bits
		while (num > 0)
		{
			count += 1;
			num = num & (num - 1);
		}
		// Display calculated result
		print("\n Output : ", (count), terminator: "");
	}
}
func main()
{
	let task: BitManipulation = BitManipulation();
	var a: Int = 43;
	var b: Int = 25;
	// a = 43    (1 0 1 0 1 1)
	// b = 25    (0 1 1 0 0 1)
	//            ↓ ↓ ↓ ↓ ↓ ↓
	//           (1 1 0 0 1 0)
	// Bit changes = 3
	task.flippedCount(a, b);
	// Case 2
	a = 12;
	b = 4;
	// a = 12    (1 1 0 0)
	// b = 4     (0 1 0 0)
	//            ↓ ↓ ↓ ↓
	//           (1 0 0 0 )
	// Bit changes =  1
	task.flippedCount(a, b);
	// Case 3
	a = 7;
	b = 7;
	// a = 7     (1 1 1 )
	// b = 7     (1 1 1 )
	//            ↓ ↓ ↓
	//           (0 0 0 )
	// Bit changes =  0
	task.flippedCount(a, b);
}
main();

Output

 Given number ( a :  43 , b :  25 )
 Output :  3
 Given number ( a :  12 , b :  4 )
 Output :  1
 Given number ( a :  7 , b :  7 )
 Output :  0
/*
  Kotlin program
  Count number of bits to be flipped to convert A to B
*/
class BitManipulation
{
	// Calculate how many bit changes are required to make equal numbers
	fun flippedCount(a: Int, b: Int): Unit
	{
		// Display given number
		print("\n Given number ( a : " + a + ", b : " + b + ") ");
		var num: Int = (a xor b);
		var count: Int = 0;
		// Count number of active bits
		while (num > 0)
		{
			count += 1;
			num = num and(num - 1);
		}
		// Display calculated result
		print("\n Output : " + (count));
	}
}
fun main(args: Array < String > ): Unit
{
	var task: BitManipulation = BitManipulation();
	var a: Int = 43;
	var b: Int = 25;
	// a = 43    (1 0 1 0 1 1)
	// b = 25    (0 1 1 0 0 1)
	//            ↓ ↓ ↓ ↓ ↓ ↓
	//           (1 1 0 0 1 0)
	// Bit changes = 3
	task.flippedCount(a, b);
	// Case 2
	a = 12;
	b = 4;
	// a = 12    (1 1 0 0)
	// b = 4     (0 1 0 0)
	//            ↓ ↓ ↓ ↓
	//           (1 0 0 0 )
	// Bit changes =  1
	task.flippedCount(a, b);
	// Case 3
	a = 7;
	b = 7;
	// a = 7     (1 1 1 )
	// b = 7     (1 1 1 )
	//            ↓ ↓ ↓
	//           (0 0 0 )
	// Bit changes =  0
	task.flippedCount(a, b);
}

Output

 Given number ( a : 43, b : 25)
 Output : 3
 Given number ( a : 12, b : 4)
 Output : 1
 Given number ( a : 7, b : 7)
 Output : 0

Resultant Output Explanation

The code provided in the question is a C program that implements the above algorithm. It uses the 'flippedCount' function to calculate the number of bit flips required for three different test cases.

  1. Test Case 1: a = 43, b = 25

    • A = 43 (Binary: 101011)
    • B = 25 (Binary: 011001)
    • XOR of A and B = 011010 (Decimal: 26)
    • Number of set bits in 26 = 3 (Bits at positions 1, 3, and 5 are set)
    • The output will be 3.
  2. Test Case 2: a = 12, b = 4

    • A = 12 (Binary: 001100)
    • B = 4 (Binary: 000100)
    • XOR of A and B = 001000 (Decimal: 8)
    • Number of set bits in 8 = 1 (Bit at position 4 is set)
    • The output will be 1.
  3. Test Case 3: a = 7, b = 7

    • A = 7 (Binary: 000111)
    • B = 7 (Binary: 000111)
    • XOR of A and B = 000000 (Decimal: 0)
    • Number of set bits in 0 = 0 (No bits are set)
    • The output will be 0.

Time Complexity of the Code

The time complexity of the provided code is determined by the number of set bits in the XOR result. Let 'n' be the number of bits in the integers 'a' and 'b'. The Brian Kernighan's algorithm, used to count the set bits, runs in O(log n) time. Therefore, the overall time complexity of the code is O(log n). It is important to note that the time complexity is not directly proportional to the magnitude of 'a' and 'b', but rather to the number of bits needed to represent them.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment