Count Minimum Bits to Flip for XOR in C++

We are given with three binary sequences A, B and C of length N. Each sequence represents a binary number. We have to find no. of flips required of bits in A and B such that XOR of A and B results in C. A XOR B becomes C.

First of all let us learn about truth table of XOR operation −

From the above table we observe that for the same values in X and Y, X XOR Y results 0 else it results 1. So this will be helpful for finding bits to be flipped in A and B to reach C. Cases will be

• If A[i]==B[i] and C[i]==0 then no flip,
• If A[i]==B[i] and C[i]==1 then flip either A[i] or B[i] and increase flip count by 1
• If A[i]!=B[i] and C[i]==0 then flip either A[i] or B[i] and increase flip count by 1
• If A[i]!=B[i] and C[i]==1 then no flip required.

Input

A[]= { 0,0,0,0 } B[]= { 1,0,1,0 } C= {1,1,1,1}

Output

Required flips : 2

Explanation

A[0] xor B[0] 0 xor 1 = 1 C[0]=1 no flip
A[1] xor B[1] 0 xor 0 = 0 C[0]=1 flip count=1
A[2] xor B[2] 0 xor 1 = 1 C[0]=1 no flip
A[3] xor B[3] 0 xor 0 = 0 C[0]=1flip count=2

Input

A[]= { 0,0,1,1 } B[]= { 0,0,1,1 } C= {0,0,1,1}

Output

Required flips : 2

Explanation

A[0] xor B[0] 0 xor 0 = 0 C[0]=0 no flip
A[1] xor B[1] 0 xor 0 = 0 C[0]=0 no flip
A[2] xor B[2] 1 xor 1 = 0 C[0]=1 flip count=1
A[3] xor B[3] 1 xor 1 = 0 C[0]=1 flip count=2

Approach used in the below program is as follows

• Arrays a[], b[] and c[] are used to store binary no’s.

• Function flipCount(int A[], int B[], int C[], int n) takes arrays a, b, c and their length n as input and returns the count of flips required in bits of either A[] or B[] to get C[] as A xor B

• Variable count represents flip count and initialized with 0.

• Using for loop traverse each bit in the cell from i = 0 to i

• For each bit A[i] and B[i]. if they are equal and C[i] is 1 increase count.

• For each bit A[i] and B[i]. if they are not equal and C[i] is 0 increase count.

• Return the count as desired result.

Example

 Live Demo

#include<bits/stdc++.h>
using namespace std;
int flipCount(int A[], int B[], int C[], int N){
   int count = 0;
   for (int i=0; i < N; ++i){
      // If both A[i] and B[i] are equal then XOR results 0, if C[i] is 1 flip
      if (A[i] == B[i] && C[i] == 1)
         ++count;
         // If Both A and B are unequal then XOR results 1 , if C[i] is 0 flip
      else if (A[i] != B[i] && C[i] == 0)
         ++count;
   }
   return count;
}
int main(){
   //N represent total count of Bits
   int N = 5;
   int a[] ={1,0,0,0,0};
   int b[] ={0,0,0,1,0};
   int c[] ={1,0,1,1,1};
   cout <<"Minimum bits to flip such that XOR of A and B equal to C :"<<flipCount(a, b, c,N);
   return 0;
}

Output

Minimum bits to flip such that XOR of A and B equal to C :2