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

Question

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

观察是，

1 ) 如果两个数字都具有 odd 个集合位，则其 XOR 将具有 even 个集合位其中的位。

2 ) 如果两个数字都具有 even 个集合位，则其 XOR 将具有 even 个集合位其中的位。

1 ) 如果两个数，其中 一个数的设置位为偶数，而另一个数另一个的设置位为奇数，则其异或将有奇数个设置位。

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

我在电脑上执行的代码是

#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 的真实性 table，并注意 table 中的四个选项中的每一个（{0, 0 => 0}，{0, 1 => 1}, {1, 0 => 1}, {1, 1, => 0}) 1s 的计数的 odd/even 奇偶校验保持不变。换句话说，如果输入有奇数个1，输出也会有奇数个1，反之亦然。

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

Answer 2

xor 只是清除公共位。设置多少位并不重要，只有多少位是通用的。

所有位都是通用的，结果为零。没有共同的位，结果是设置位的总和。

没有基于输入奇偶校验的结论，除非您也考虑了公共位的奇偶校验。

Answer 3

感谢所有试图回答的人。

我们可以这样给出证明，

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

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

偶数 + 奇数 - 偶数 = 奇数

奇数+奇数-偶数=偶数

偶数+偶数-偶数=偶数

Answer 4

一个可能的证明是基于对 xor 是交换运算符的观察，所以 (xor digits of x) xor (xor digits of y) = xor of digits of (x xor y)

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

parity of set bits after xor of two numbers

c++

xor

parity