为什么此加法代码（使用按位运算）在 Java 中有效

Why this code for addition(using bitwise operation) works in java

提问by Sunny

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

            a = a ^ b; 

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

This is the code to calculate sum of two integers using bitwise operation.

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

If i calculate manually/programmatically, i see it works for every integer. But i am not able to figure out any relation between intermediate value of aand carry. and why carry is multiplied by 2 to assign to b?

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

PS: I found the one answer here Bitwise Multiply and Add in Javabut this is for multiplication and not for addition.

PS：我在这里找到了一个答案 ，在 Java 中按位乘法和加法但这是乘法而不是加法。

回答by Tobber

First recall addition in primary school. e.g. 26 + 147 = 173. You start by 6+7=13, so you put 3 in the sum, and carry the one, and so forth - that is: you add two digits and carry a one if necessary.

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

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

The code does almost the same thing on binary numbers, but with a small tweak. Instead of taking one digit position at a time, it takes all in one go. Instead of including the carry from position i-1 in i (i.e. including 1 when adding 2 and 4), the code add all caries in a second iteration. So what it does is: 026+147 = 163 + 010 = 173 + 000

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

For the binary numbers a=6=00110 and b=7=00111 you get

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

First you find the carries; that is all positions where both aand bhas its bit set: int carry = (a & b) ;

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

Then id does the addition of digits, ignoring the carry, and stores it in a: a = a ^ b;This will respond to 6+7=3in the example.

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

The last part shifts the carry to the next digit position, i.e. ensuring the 1-carry in the example is "moved" from the 1's to the 10's: carry << 1;

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

The while loop continues as long as there are carries that has not been included in the sum.

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

回答by IanPudney

The variables band carryare used for "carrying" extra digits. For example, in binary, 1+1 = 10, but 10is a two-digit number. The 1in 10must be placed in the next digit to the left. That's what the while()loop does in your program. Wherever there are 1digits in the same place (a & b), carryis set to the XOR of b(a ^ b). this gives each digit the value of 1only if either aor b, but not both, has the value of 2. (When doing binary arithmetic, that's exactly what happens; 1+1 = 10, so since two 1s are being added together, the ones place is 0). After that, carry << 1(carry*2or carryshifted left by one) is assigned to b. The loop then repeats, using the new values of aand buntil bis zero (which means carryis also zero).

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

回答by catvir

Definately think of all numbers in here in binary system.

绝对想到这里的所有数字都是二进制系统。

What You would usually like to find out in such code is a "loop invariant". In this case, You would like to see that a + b is constant after every iteration. Thus if b becomes 0 and we leave the loop, a must be equal to the sum of original a and b. The next step is to make sure that the loop will eventually terminate. We'll come back to this later, first let's figure out the invariant part, which in this case is using the equality:

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

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

where in the loop new a will be equal to old a ^ b and new b will be 2 * (a & b), which is the same as (a & b) << 1. That's the essense of Your problem - figuring out this equality. It's exactly how You do the addition.

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

I'll present two solutions. In both I'll use a simple fact that:

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

x + y = x ^ y

Whenever x and y have no common bits set.

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

The short way to see this formally is to note that:

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

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)

The lengthy solution uses mathematical induction as follows (this might be considered an overkill by some, but in my option it's worth to know it):

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

First make sure it works with a and b both equal to zero (You might also try for one bit numbers which explain a lot of how this algorithm works). Never forget about this step when using mathematical induction.

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

Next, assume this works for n-1 bit numbers, we've got to show that it works for n bit ones too. Now write a = 2a' + a'' = 2a' ^ a'' and b = 2b' + b'' = 2b' ^ b'' where a'', b'' are in set {0, 1} (then 2a' and a'' have no common bits set!). Then:

接下来，假设这适用于 n-1 位数字，我们必须证明它也适用于 n 位数字。现在写 a = 2a' + a'' = 2a' ^ a'' and 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

Now the last thing to check is that this loop really terminates. to see this use the fact that at each step both a and b are non-negative, and that this remains true after each iteration.

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

Therefore we've got that b <= a + b. Next note that after n steps b has to be ending with n zeroes. Thus we cannot do more than log_2(a+b) steps since we'd get either b = 0 or b = k * 2*n >= 2*n > 2**log_2(a+b) = a+b contradicting assumption. Here ** denotes exponentiation of course.

因此我们得到 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 矛盾假设。这里**当然表示求幂。

In Java this algorithm would also work on negative integers. This is because of how negative integers are stored in Java and in most programming languages Here, the addition and subtraction of signed and unsigned numbers works identically on bits, therefore code that works for unsigned numbers will also work for signed.

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

回答by bonger22

It relies on the fact that 1+1=10 (bitwise), i.e. "if an addition implies a carry bit, then sum current's digit column must be zero". Think of the "<<" operator as "carry the bits to the left" instead of thinking "multiply an int by 2"

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

Here's a prosaic description of the code.

这是代码的平淡描述。

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.

回答by sivag1

Yes, like many answers here, it works like rudimentary school math for adding two numbers. But in Binary way.

是的，就像这里的许多答案一样，它的工作原理类似于将两个数字相加的初级数学。但以二进制方式。

1. What does a&b give us? It gives ones at all places which will trigger a carry forward. For examples, adding 1101 and 0101, only the 0th and 2nd position from right triggers carry forward. So only that will be 0101 which is obtained by a&b. But when doing carry in normal addition, we move one position left. That is why in 3rd statement of code, the carry is moved one position left. So carry becomes 01010.

2. What does a^b give us? Any bit that is not counted above is included. In the above step, we included impact of 0th and 2nd bit. Now we need to include other bits which have 1. That will be 3rd from right giving is 1000. The value assigned to a becomes 1000.

Now all we have to do is add these again, using the same steps above.

3. Adding 01010 and 01000. Only common one is 3rd position, so a&b gives 01000 and carry eventually becomes 10000 after the shift.

4. To count the remaining bits, a^b becomes 00010 and gets assigned to a.

Loop continues. As carry above is not zero yet.

5. Adding 10000 and 00010. No common 1's bit. So carry becomes 0.

6. a^b becomes 10010 and gets assigned to a.

7. As carry is zero, whatever in a, which is 10010 becomes the answer!

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

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

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

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

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

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

5. 将 10000 和 00010 相加。没有共同的 1 位。所以进位变为0。

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

7. 由于进位为零，无论在 a 中，即 10010 都成为答案！

Much better to understand with examples, smaller examples.

用例子更好地理解，更小的例子。