Proof for the bitwise XOR of two numbers to have Odd Number of set bits only when exactly one of them have odd number of bits?

565 Views Asked by At

I was doing some Algorithms Contest Question ( OffCourse it is not live now), Where I encountered this amazing Pattern that Two Non Negative Numbers $A$ and $B$ whose Exclusive XOR represented by $C=A \oplus B$ is going to have Odd Number of Set bits Only when exactly one of them A or B have odd Number of Set bits for All other cases the C is going to have Even Number of Set Bits..
You can Take Any example of your wish A=2 and B=9
where A has odd number of set bits and B has even set Bits without even xoring them I can say $A \oplus B$ is going to have odd number of bits.
I am not able to prove it in my head that why is it true? It will appreciated if someone can provide a more concrete proof..