使用位操作添加两个数字(Add two numbers using bit manipulation)

使用位操作添加两个数字(Add two numbers using bit manipulation)

我正在研究GeeksForGeeks的以下练习题：

编写一个返回两个整数之和的函数Add（）。 该函数不应使用任何算术运算符（+，++， - ， - ，..等）。

C＃中给出的解决方案是：

public static int Add(int x, int y) { // Iterate till there is no carry while (y != 0) { // carry now contains common set bits of x and y int carry = x & y; // Sum of bits of x and y where at least one of the bits is not set x = x ^ y; // Carry is shifted by one so that adding it to x gives the required sum y = carry << 1; } return x; }

看看这个解决方案，我理解它是如何发生的; 我可以跟随调试器并在它们到来之前预测值的变化。 但经过几次走过，我仍然不明白为什么会发生这种情况。 如果要在面试中提出，我将不得不依靠记忆来解决它，而不是实际理解算法是如何工作的。

有人可以帮助解释为什么我们在某些点使用某些运算符以及这些总计假设代表什么？ 我知道代码中已有评论，但我显然遗漏了一些东西......

I'm working on the following practice problem from GeeksForGeeks:

Write a function Add() that returns sum of two integers. The function should not use any of the arithmetic operators (+, ++, –, -, .. etc).

The given solution in C# is:

public static int Add(int x, int y) { // Iterate till there is no carry while (y != 0) { // carry now contains common set bits of x and y int carry = x & y; // Sum of bits of x and y where at least one of the bits is not set x = x ^ y; // Carry is shifted by one so that adding it to x gives the required sum y = carry << 1; } return x; }

Looking at this solution, I understand how it is happening; I can follow along with the debugger and anticipate the value changes before they come. But after walking through it several times, I still don't understand WHY it is happening. If this was to come up in an interview, I would have to rely on memory to solve it, not actual understanding of how the algorithm works.

Could someone help explain why we use certain operators at certain points and what those totals are suppose to represent? I know there are already comments in the code, but I'm obviously missing something...

最满意答案

在每次迭代中，您都有以下步骤：

carry <- x & y // mark every location where the addition has a carry x <- x ^ y // sum without carries y <- carry << 1 // shift the carry left one column

在下一次迭代中， x保持除了进位之外的整个和，它们在y中。 这些载物正好向左一列撞击，就像你在纸上做了一样。 继续这样做，直到不再需要担心进位。

非常简单地说， 除了从右到左工作之外 ，它会像你或我在纸上做的那样添加，它会并行执行所有的操作。

At each iteration, you have these steps:

carry <- x & y // mark every location where the addition has a carry x <- x ^ y // sum without carries y <- carry << 1 // shift the carry left one column

On the next iteration, x holds the entire sum except for the carry bits, which are in y. These carries are properly bumped one column to the left, just as if you were doing the addition on paper. Continue doing this until there are no more carry bits to worry about.

Very briefly, this does the addition much as you or I would do it on paper, except that, instead of working right to left, it does all the bits in parallel.