请解释公式x+y = x^y + 2*(x&y)的成立原因及乘2逻辑

二进制加法的本质可以拆成两部分：本位计算结果和进位输出，这个公式就是把这两部分单独算出后再合并。

• 先看异或（x^y）：异或的规则是两个二进制位不同时得1，相同时得0。这正好对应不考虑进位的加法结果——比如0+1得1，1+0得1，0+0得0，1+1得0（先不管进位），完全就是无进位的本位相加结果。

• 再看按位与（x&y）：按位与只有当两个二进制位都是1时才得1，这时候两个1相加会产生进位，进位是向高位进1。比如某一位是1+1，进位的1实际上要加到更高一位，相当于这个进位的数值是当前位的1乘以2（左移一位）。所有产生进位的位加起来就是x&y，把这些进位都挪到正确的高位，就是给x&y乘以2。

把无进位的本位结果（x^y）和所有进位的总和（2*(x&y)）加起来，就得到了完整的加法结果x+y。

举几个实际例子验证：

• x=3（二进制011），y=5（二进制101）：
  x^y = 011 ^ 101 = 110（十进制6），x&y = 011 & 101 = 001（十进制1），2*(x&y)=2，6+2=8，正好等于3+5=8。
• x=6（110），y=4（100）：
  x^y=010（2），x&y=100（4），2*4=8，2+8=10，和6+4=10完全吻合。

说白了，这个公式就是把加法里的“无进位部分”和“进位部分”分开计算再合并，乘以2就是把进位放到它该去的高位上。

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