请求证明：两个数异或后set bits的奇偶性规律

Great observation! Your test results perfectly align with a fundamental property of binary parity and XOR operations. Let's break down the proof clearly, starting with some definitions to make things concrete.

Key Definitions #

Let’s define a helper function for any integer n:

• P(n) = __builtin_popcount(n) % 2
  This is just the parity of the number of set bits (1s) in n: P(n) = 1 if there’s an odd number of 1s, P(n) = 0 if even.

Your three observations can be rephrased as a single, unified rule:

P(a ^ b) = P(a) XOR P(b)

Where the XOR here refers to logical bitwise XOR (0 XOR 0 = 0, 0 XOR 1 = 1, 1 XOR 0 = 1, 1 XOR 1 = 0). Proving this rule will automatically validate all three of your original observations.

Step-by-Step Proof #

Let’s examine each binary bit position k (starting from 0 for the least significant bit) for integers a and b:

1. Case 1: a and b have identical bits at position k

   • If both bits are 0: a^b has 0 at position k (no contribution to P(a^b)). P(a) and P(b) each get +0, so their total contribution mod 2 is 0.
   • If both bits are 1: a^b has 0 at position k (no contribution to P(a^b)). P(a) and P(b) each get +1, so their total contribution mod 2 is 2 ≡ 0.
   • In both subcases: the contribution to P(a^b) equals the contribution to P(a) + P(b) (mod 2).

2. Case 2: a and b have different bits at position k

   • One bit is 0, the other is 1: a^b has 1 at position k (contributes +1 to P(a^b)). P(a) gets +1 and P(b) gets +0 (or vice versa), so their total contribution mod 2 is 1.
   • Here again: the contribution to P(a^b) equals the contribution to P(a) + P(b) (mod 2).

Summing Up All Bits #

When we sum contributions across all bit positions:

• P(a^b) is the total number of 1s in a^b mod 2 → sum of contributions from each bit in a^b.
• P(a) + P(b) mod 2 is the sum of all bit contributions from a and b mod 2.

Since every bit position contributes the same value to both sums (mod 2), we get:
P(a^b) ≡ P(a) + P(b) (mod 2)

But addition mod 2 is exactly the logical XOR operation. This simplifies to:
P(a^b) = P(a) XOR P(b)

Mapping Back to Your Observations #

Now let’s connect this rule to your three original conclusions:

• Observation 1: If P(a)=1 and P(b)=1, then P(a^b)=1 XOR 1=0 (even set bits) ✔️
• Observation 2: If P(a)=0 and P(b)=0, then P(a^b)=0 XOR 0=0 (even set bits) ✔️
• Observation 3: If one of P(a)/P(b) is 0 and the other is 1, then P(a^b)=0 XOR1=1 (odd set bits) ✔️

Verifying Your Code Output #

Your code groups pairs by in = (x<<1)|y where x=P(i), y=P(j):

• vec[0] (x=0, y=0): All values are 0 → matches Observation 2
• vec[1] (x=0, y=1): All values are 1 → matches Observation 3
• vec[2] (x=1, y=0): All values are 1 → matches Observation 3
• vec[3] (x=1, y=1): All values are 0 → matches Observation 1

Which exactly matches the output you described—perfect confirmation of the rule!

内容的提问来源于stack exchange，提问作者Kavar Rushikesh