时间戳

首页 > 解决方案 > 两个数异或后设置位的奇偶校验

c++ - 两个数异或后设置位的奇偶校验

问题描述

我通过在 C++ 中进行测试发现了一个观察结果。

观察是，

1）如果两个数字中都有奇数个设置位，那么它的 XOR 将有偶数个设置位。

2）如果两个数字中的设置位为偶数，则其 XOR中的设置位为偶数。

1 ) 如果两个数，其中一个数具有偶数个设置位，另一个具有奇数个设置位， 则其 XOR 将具有奇数个设置位。

我无法证明这一点。我想证明这一点。请帮我。

我在我的电脑上执行的代码是

#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int> vec[4];
    for(int i=1;i<=100;i++){
       for(int j=i+1;j<=100;j++){ 
         int x=__builtin_popcount(i)%2;
         int y=__builtin_popcount(j)%2;
         int in=0;
         in|=(x<<1);
         in|=(y<<0);
         int v=__builtin_popcount(i^j)%2;
         vec[in].push_back(v);
      }
    }
      for(int i=0;i<4;i++){
         for(int j=0;j<vec[i].size();j++) cout<<vec[i][j] << " ";
         cout << endl;
      }
   return 0;
}

它给了我

第一行 100 个零 第二行 100 个零 第三行 100 个零 第四行 100 个零

如果对理解代码有疑问，请在评论中告诉我。

标签： c++xorparity

解决方案

这种行为反映了一个易于证明的算术事实：

  • 两个奇数相加得到偶数
  • 两个偶数相加得到偶数
  • 当您将奇数添加到偶数时，您会得到一个奇数。

有了这个事实，考虑 的真值表XOR，并注意对于表中的四个选项（{0, 0 => 0}、{0, 1 => 1}、{1, 0 => 1}、{1, 1, => 0}）中的每一个， s 计数的奇/偶校验1保持不变。换句话说，如果输入有奇数个1s，输出也将有奇数个1s，反之亦然。

这个观察解释了为什么你会观察到结果：将XOR两个数字设置为N和M将产生一个与 具有相同奇/偶校验的数字N+M。

推荐阅读