parity of set bits after xor of two numbers

Question

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.

Answer 1

This behavior mirrors an easy-to-prove arithmetical fact:

• When you add two odd numbers, you get an even number,
• When you add two even numbers, you get an even number,
• When you add an odd number to an even number, you get an odd number.

With this fact in hand, consider the truth table of XOR, and note that for each of the four options in the table ({0, 0 => 0}, {0, 1 => 1}, {1, 0 => 1}, {1, 1, => 0}) the odd/even parity of the count of 1s remains invariant. In other words, if the input has an odd number of 1s, the output will have an odd number of 1s as well, and vice versa.

This observation explains why you observe the result: XORing two numbers with the counts of set bits of N and M will yield a number that has the same odd/even parity as N+M.