按位运算添加

Question

你能帮我弄清楚下面的表达式为什么是真的:x + y = x ^ y +(x&y)<< 1

我正在寻找一些来自按位逻辑的规则来解释这个数学等价物.

Answer 1

这就像解决一个普通的基础10添加问题955 + 445,首先单独添加所有列并丢弃携带1的:

    955
    445
  -----
    390

然后查找应该携带的所有列1:

    955
    445
  -----
    101

将其移动并将其添加到原始结果中:

   390
+ 1010
------
  1400

所以基本上你是在做加法但忽略了所有进行1的,然后加入后面的,作为一个单独的步骤.

在基数2中,^当任一位为a时,XOR()正确地执行加法0.当两个位都是时1,它执行加法而不进位,就像我们在上面的第一步中所做的那样.

x ^ y正确地将所有位添加到何处x并且y不是两者1:

   1110111011
^  0110111101
-------------
   1000000110      (x ^ y)

x & y给出了1所有列中两个位都是1的列.这些正是我们错过了一个进位的列:

   1110111011
&  0110111101
-------------
   0110111001      (x & y)

当然,当你进行1添加时,你将它移到一个地方,就像你添加10基地一样.

   1000000110      (x ^ y)
+ 01101110010    + (x & y) << 1
-------------
  10101111000