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

Question

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

观察是，

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

2 ) 如果两个数字中都有偶数个设置位，那么它的异或将有偶数个设置位。

1 ) 如果两个数一个数的置位位数为偶数，而另一个数的置位位数为奇数，则其 XOR 将为奇数 strong> 其中设置的位数。

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

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

#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

这种行为反射(reflect)了一个易于证明的算术事实:

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

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

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