求证x,y>0时位运算等式x + y = x & y + x | y的证明及原理

嘿，这个问题问得特别巧妙——我第一次在竞赛里见到这个等式的时候也眼前一亮，咱们从二进制位的底层逻辑入手，一步步把它拆明白！

核心直觉：加法的两个组成部分 #

咱们先回忆一下二进制加法的本质：每一位的计算其实包含两个部分：

• 无进位的逐位相加：两个位相加时，不考虑低位来的进位，结果就是「异或」(x ^ y)的结果（比如1+1无进位相加得0，0+1得1，和异或规则完全一致）；
• 进位值：只有当两个位都是1的时候，才会向高位进1，这个进位的标记就是「与」(x & y)的结果，实际进位值是(x & y) << 1（因为进位要往高一位走）。

所以加法的完整表达式其实是：

x + y = (x ^ y) + ((x & y) << 1)

推导等式：把或运算拆解 #

现在看等式右边的x & y + x | y，咱们先拆解x | y（按位或）的含义：
按位或的每一位，只要x或y有一个是1，结果就是1。它可以拆成两部分：

• 只有一个位是1的情况：这部分就是x ^ y（异或，不同为1）；
• 两个位都是1的情况：这部分就是x & y（与，同为1）。

因为这两部分没有重叠（一个位不可能同时「只有一个1」和「两个都是1」），所以可以直接相加：

x | y = (x ^ y) + (x & y)

把这个代入等式右边：

x & y + x | y = (x & y) + (x ^ y + x & y) = (x ^ y) + 2*(x & y)

而2*(x & y)其实就是(x & y) << 1（左移一位等价于乘2），这不就是咱们刚才的加法表达式吗？所以：

x & y + x | y = (x ^ y) + ((x & y) << 1) = x + y

逐位验证：更直观的确认 #

咱们可以把每一位的四种可能情况单独拿出来验证，确保每一位的计算都符合等式：

• 当x位=0，y位=0：
  • x+y的位贡献：0+0=0
  • x&y + x|y的位贡献：0+0=0 → 相等
• 当x位=0，y位=1：
  • x+y的位贡献：0+1=1
  • x&y + x|y的位贡献：0+1=1 → 相等
• 当x位=1，y位=0：
  • 同上，结果都是1 → 相等
• 当x位=1，y位=1：
  • x+y的位贡献：1+1=2（对应二进制本位0，进位1到高位）
  • x&y + x|y的位贡献：1+1=2 → 完全匹配

因为每一位的计算都严格相等，所以整体的数值相加自然也相等，不管x和y是多大的正整数，这个等式都成立。

这样拆解下来是不是就完全清晰了？本质上就是把加法的进位和无进位部分，用位运算的组合重新做了一次表达，确实是个非常优美的位运算小技巧！

内容的提问来源于stack exchange，提问作者Naveen Kumar Vunnam