12 
public int add(int a, int b){  
        while (b != 0){
            int carry = (a & b) ;

            a = a ^ b; 

            b = carry << 1;
        }
        return a;
 }

这是使用按位运算计算两个整数之和的代码。

如果我手动/以编程方式计算，我发现它适用于每个整数。但我无法弄清楚 和 的中间值之间的任何a关系carry。为什么进位乘以 2 分配给b？

PS：我在这里找到了一个答案 Bitwise Multiply and Add in Java 但这适用于乘法而不是加法。

4

5 回答 5

20

第一次回忆小学的加法。例如 26 + 147 = 173。你从 6+7=13 开始，所以你把 3 放在总和中，然后进位，依此类推——也就是说：你加上两位数，必要时进位。

carry:  1
a:      26
b:     147
-----------------
sum:   173

该代码对二进制数执行几乎相同的操作，但稍作调整。它不是一次占据一个数字位置，而是一次完成。代码不是在 i 中包含从位置 i-1 开始的进位（即在添加 2 和 4 时包含 1），而是在第二次迭代中添加所有龋齿。所以它的作用是：026+147 = 163 + 010 = 173 + 000

对于二进制数 a=6=00110 和 b=7=00111 你得到

首先，您找到携带；这是所有位置都设置了a和b的位置：int carry = (a & b) ;

然后 id 进行数字相加，忽略进位，并将其存储在a:a = a ^ b;这将6+7=3在示例中响应。

最后一部分将进位移动到下一个数字位置，即确保示例中的 1 进位从 1“移动”到 10： carry << 1;

只要有未包含在总和中的进位，while 循环就会继续。

于 2013-06-27T11:53:04.817 回答
2

变量b和carry用于“携带”额外的数字。例如，在二进制中，1+1 = 10, but10是一个两位数。1in10必须放在左边的下一位。这就是while()循环在你的程序中所做的。凡在同一位置有1数字的地方 ( a & b)，carry都设置为b( a ^ b) 的 XOR。这给每个数字的值1只有当一个a或b，但不是两个都具有 2 的值时。（在进行二进制算术时，这正是发生的情况；1+1 = 10，所以由于两个1s 被加在一起，所以个位是0）。之后，carry << 1（carry*2或carry左移一位）分配给b. 然后循环重复，使用a和b直到b为零（这意味着carry也是零）的新值。

于 2013-06-27T11:45:19.600 回答
2

一定要考虑二进制系统中的所有数字。

您通常希望在此类代码中找到“循环不变量”。在这种情况下，您希望看到 a + b 在每次迭代后都保持不变。因此，如果 b 变为 0 并且我们离开循环，则 a 必须等于原始 a 和 b 的总和。下一步是确保循环最终终止。我们稍后会回到这个，首先让我们找出不变部分，在这种情况下使用相等：

a + b = (a ^ b) + 2 * (a & b)

在循环中，新 a 将等于旧 a ^ b，新 b 将是 2 * (a & b)，这与 (a & b) << 1 相同。这就是你问题的本质 - 弄清楚这种平等。这正是你做加法的方式。

我将介绍两种解决方案。在两者中，我将使用一个简单的事实：

x + y = x ^ y

每当 x 和 y 没有设置公共位时。

正式看到这一点的简短方法是注意：

a + b = a + b - 2(a & b) + 2(a & b)
= (a - (a & b)) + (b - (a & b)) + 2(a & b)
= (a - (a & b)) ^ (b - (a & b)) + 2(a & b)
= (a ^ (a & b)) ^ (b ^ (a & b)) + 2(a & b)
= a ^ b + 2(a & b)

冗长的解决方案使用如下数学归纳法（这可能被某些人认为是矫枉过正，但在我看来，值得知道它）：

首先确保它在 a 和 b 都等于 0 的情况下工作（您也可以尝试使用一位数字来解释该算法的工作原理）。使用数学归纳法时永远不要忘记这一步。

接下来，假设这适用于 n-1 位数字，我们必须证明它也适用于 n 位数字。现在写 a = 2a' + a'' = 2a' ^ a'' 和 b = 2b' + b'' = 2b' ^ b'' 其中 a'', b'' 在集合 {0, 1} 中（那么 2a' 和 a'' 没有设置公共位！）。然后：

(a ^ b) + 2(a & b) = (2a' ^ a'' ^ 2b' ^ b'') + 2((2a'' ^ a') & (2b'' ^ b')) =
(2a' ^ 2b') ^ (a'' ^ b'') + 2((2a'' & 2b'') ^ (a'' & b'')) = 
(2a' ^ 2b') + (a'' ^ b'') + 2((2a'' & 2b'') + (a'' & b'')) =
(2a' ^ 2b') + 2((2a'' & 2b'') + (a'' ^ b'') + (a'' & b'')) =
2a' + 2b' + a'' + b'' = a + b

现在要检查的最后一件事是这个循环真的终止了。要看到这一点，请使用在每个步骤中 a 和 b 都是非负的事实，并且在每次迭代后仍然如此。

因此我们得到了 b <= a + b。接下来请注意，在 n 步之后 b 必须以 n 个零结尾。因此我们不能做超过 log_2(a+b) 步骤，因为我们会得到 b = 0 或 b = k * 2* n >= 2 *n > 2**log_2(a+b) = a+b 矛盾假设。这里**当然表示取幂。

在 Java 中，该算法也适用于负整数。这是因为负整数在 Java 和大多数编程语言中的存储方式在这里，有符号数和无符号数的加法和减法在位上的工作方式相同，因此适用于无符号数的代码也适用于有符号数。

于 2013-06-27T13:43:37.153 回答
1

它依赖于 1+1=10（按位）这一事实，即“如果加法意味着进位，则求和当前的数字列必须为零”。将“<<”运算符视为“将位向左移动”而不是“将 int 乘以 2”

这是代码的平淡无奇的描述。

carry = Ignore those bits that will produce carry bits (because their sum in the current "column"  will be 0), but collect the carry bits. 
a = Add those bits of a and b that won't produce a carry bit (i.e. use XOR)
b = Carry the carry bits one column left.
于 2013-06-27T12:08:22.107 回答
0

是的，就像这里的许多答案一样，它就像小学数学一样，可以将两个数字相加。但以二进制方式。

  1. a&b 带给我们什么？它在所有地方都提供了会触发结转的地方。例如，添加 1101 和 0101，只有右触发器的第 0 位和第 2 位向前移动。所以只有 a&b 获得的 0101。但是在正常加法中进行进位时，我们将左移一个位置。这就是为什么在第三条代码语句中，进位向左移动了一位。所以进位变成01010。

  2. a^b 给了我们什么？上面未计算的任何位都包括在内。在上述步骤中，我们包括了第 0 位和第 2 位的影响。现在我们需要包括其他具有 1 的位。这将是从右边给出的第 3 位是 1000。分配给 a 的值变为 1000。

现在我们要做的就是使用上述相同的步骤再次添加这些。

  1. 添加 01010 和 01000。只有共同的一个是第 3 位，所以 a&b 给出 01000，并且在移位后进位最终变为 10000。

  2. 要计算剩余位，a^b 变为 00010 并分配给 a。

循环继续。由于上面的进位还不是零。

  1. 添加 10000 和 00010。没有共同的 1 位。所以进位变成0。

  2. a^b 变为 10010 并分配给 a。

  3. 由于进位为零，a 中的任何内容，即 10010 都将成为答案！

通过示例，较小的示例可以更好地理解。

于 2015-09-18T20:51:39.270 回答