给出三个长度为N的二进制序列A,B和C。每个序列代表一个二进制数。我们必须找到没有。对A和B中的位进行所需的翻转,以使A和B的XOR导致C。XOR B变为C。
首先让我们了解XOR运算的真值表-
X | ÿ | X XOR Y |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
从上表中我们观察到,对于X和Y中相同的值,X XOR Y结果为0,否则结果为1。因此,这对于查找要在A和B中翻转到C的位将很有帮助。
如果A [i] == B [i]并且C [i] == 0,则没有翻转,
如果A [i] == B [i]并且C [i] == 1,则翻转A [i]或B [i]并将翻转数增加1
如果A [i]!= B [i]并且C [i] == 0,则翻转A [i]或B [i]并将翻转计数增加1
如果A [i]!= B [i]和C [i] == 1,则不需要翻转。
A[]= { 0,0,0,0 } B[]= { 1,0,1,0 } C= {1,1,1,1}
输出结果
Required flips : 2
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
A[]= { 0,0,1,1 } B[]= { 0,0,1,1 } C= {0,0,1,1}
输出结果
Required flips : 2
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
数组a [],b []和c []用于存储二进制编号。
函数flipCount(int A [],int B [],int C [],int n)以数组a,b,c及其长度n作为输入,并以A []或B的位返回所需的翻转次数[]获得C []作为A xor B
可变计数表示翻转计数,并以0初始化。
使用for循环遍历单元中从i = 0到i的每个位
对于每个比特A [i]和B [i]。如果它们相等且C [i]为1增加计数。
对于每个比特A [i]和B [i]。如果它们不相等并且C [i]为0,则增加计数。
返回计数作为所需结果。
#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){ //如果A [i]和B [i]相等,则XOR结果为0,如果C [i]为1,则 if (A[i] == B[i] && C[i] == 1) ++count; //如果A和B都不相等,则XOR结果为1,如果C [i]为0,则翻转 else if (A[i] != B[i] && C[i] == 0) ++count; } return count; } int main(){ //N代表总位数 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 <<"翻转的最小位数,以使A和B的XOR等于C:"<<flipCount(a, b, c,N); return 0; }
输出结果
翻转的最小位数,以使A和B的XOR等于C:2