c++xorparity

parity of set bits after xor of two numbers


I found an observation by testing in C++.

Observation is ,

1 ) If two numbers where both numbers have odd number of set bits in it then its XOR will have even number of set bits in it.

2 ) If two numbers where both numbers have even number of set bits in it then its XOR will have even number of set bits in it.

1 ) If two numbers where one number has even number of set bits and another has odd number of set bits then its XOR will have odd number of set bits in it.

I could not prove it. I want to prove it. Please help me.

Code that i executed on my computer is

#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;
}

It gives me

100 zeros in first line 100 ones in second line 100 ones in third line 100 zeros in fourth line

If there is a doubt in understanding the code then please tell me in comments.


Solution

  • Thanks all who tried to answer.

    We can give proof like this,

    Suppose N is number of set bits in first number and M is set bits in second number.

    Then set bits in XOR of these two numbers is N+M - 2 (Δ) where is delta is total number of bit positions where both of numbers have set bit. Now this expression explains every thing.

    even + odd - even = odd

    odd + odd - even = even

    even + even - even = even