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)
{
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
// 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
// Case 3
a = 7;
b = 7;
// a = 7     (1 1 1 )
// b = 7     (1 1 1 )
//            ↓ ↓ ↓
//           (0 0 0 )
// Bit changes =  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``````
``````// 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()
{
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
// 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
// Case 3
a = 7;
b = 7;
// a = 7     (1 1 1 )
// b = 7     (1 1 1 )
//            ↓ ↓ ↓
//           (0 0 0 )
// Bit changes =  0
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()
{
\$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
// 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
// Case 3
\$a = 7;
\$b = 7;
// a = 7     (1 1 1 )
// b = 7     (1 1 1 )
//            ↓ ↓ ↓
//           (0 0 0 )
// Bit changes =  0
}
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)
{
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
// 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
// Case 3
a = 7;
b = 7;
// a = 7     (1 1 1 )
// b = 7     (1 1 1 )
//            ↓ ↓ ↓
//           (0 0 0 )
// Bit changes =  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``````
``````/*
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 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
// 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
// Case 3
a = 7;
b = 7;
// a = 7     (1 1 1 )
// b = 7     (1 1 1 )
//            ↓ ↓ ↓
//           (0 0 0 )
// Bit changes =  0
}
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() :
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
#  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
#  Case 3
a = 7
b = 7
#  a = 7     (1 1 1 )
#  b = 7     (1 1 1 )
#             ↓ ↓ ↓
#            (0 0 0 )
#  Bit changes =  0

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()
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
#  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
#  Case 3
a = 7
b = 7
#  a = 7     (1 1 1 )
#  b = 7     (1 1 1 )
#             ↓ ↓ ↓
#            (0 0 0 )
#  Bit changes =  0
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
// 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
// Case 3
a = 7;
b = 7;
// a = 7     (1 1 1 )
// b = 7     (1 1 1 )
//            ↓ ↓ ↓
//           (0 0 0 )
// Bit changes =  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``````
``````/*
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()
{
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
// 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
// Case 3
a = 7;
b = 7;
// a = 7     (1 1 1 )
// b = 7     (1 1 1 )
//            ↓ ↓ ↓
//           (0 0 0 )
// Bit changes =  0
}
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 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
// 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
// Case 3
a = 7;
b = 7;
// a = 7     (1 1 1 )
// b = 7     (1 1 1 )
//            ↓ ↓ ↓
//           (0 0 0 )
// Bit changes =  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``````

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

Categories
Relative Post