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

Question

我通过在 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 个零

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

Answer 1

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

• 两个奇数相加得到偶数
• 两个偶数相加得到一个偶数，
• 当你把一个奇数加到一个偶数上时，你会得到一个奇数。

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

此观察结果解释了您观察结果的原因：将XOR两个数字设置为N和M将产生一个与 具有相同奇数/偶数奇偶校验的数字N+M。

Answer 2

感谢所有试图回答的人。

我们可以给出这样的证明，

假设 N 是第一个数字中的设置位数，M 是第二个数字中的设置位数。

然后这两个数字的 XOR 中的设置位是 N+M - 2 (Δ) 其中 delta 是两个数字都设置了位的位位置总数。现在这个表达解释了一切。

偶数 + 奇数 - 偶数 = 奇数

奇数 + 奇数 - 偶数 = 偶数

偶数 + 偶数 - 偶数 = 偶数