不使用+运算符，最好的方法是什么来实现两个数字相加？

Question

我的朋友和我正在互相出谜题，我不知道该如何解决这个问题。 我的假设是可能需要使用一些位运算符，但我不确定。

- user23126

---

你可以通过循环查看每个位，直到值为0（然后你将处理所有位）。首先将其转换为无符号。我能赢得奖品吗？ - Andrew Rollings

谢谢。你的奖励是知道你帮助了一个处于困境中的女士的知识。 - user23126

如果不能使用运算符，那么按位运算符也被排除了吗？还是只有+-*/？ - Vilx-

一架算盘可以很好地完成这个任务，而且它不需要使用任何电力！ - Steven A. Lowe

我将使用std::plus<int>()(a, b)。 - Johannes Schaub - litb

Answer 1

在C语言中，使用位运算符：

#include<stdio.h>

int add(int x, int y) {
    int a, b;
    do {
        a = x & y;
        b = x ^ y;
        x = a << 1;
        y = b;
    } while (a);
    return b;
}


int main( void ){
    printf( "2 + 3 = %d", add(2,3));
    return 0;
}

XOR (x ^ y) 是没有进位的加法。(x & y) 是每个比特位的进位。 (x & y) << 1 是每个比特位的进位。循环一直将进位与和相加，直到所有比特位的进位都为零。

- CMS

---

add(6, -3) 应该可以工作，您可以在这里尝试代码：http://codepad.org/iWSRSsUn - Christian C. Salvadó

左移一个负数是未定义行为，虽然在许多处理器上可以正常运行，但不能保证，你应该在回答中指出这一点。另外，你可以在printf语句中添加\n。除此之外，回答不错。 - Robert Gamble

@pomeranian.myopenid.com，这很可能是由于Python中左移运算符的处理方式。与其在整数位上达到上限并将最高位设置为负数以使数字变为负数，它会变成正长整数。 - Lara Dougan

从计算机科学的角度来看，理论上，加法并不比减法更为特殊。 关键在于负数的表示方式，因为10-5与10+（-5）没有任何区别。 最可能需要研究二进制补码，即一的补码加1，这与反转所有位并加1相同。 请记住，这种方法通常会导致溢出，但这不应该是问题。 我应该提到，负数可以以不同的方式表示，因此方法也需要不同。 - Zacariaz

@ChristianC.Salvadó 我知道你很久以前就回答了。但是，我有一个问题。我们是否可以使用位运算符进行加法运算，但不使用任何循环？ - F.C. Akhi

Answer 2

int add(int a, int b) {
   const char *c=0;
   return &(&c[a])[b];
}

- ackb

---

我不太明白这个是怎么工作的，能否给我解释一下？谢谢！ - ffledgling

@cantaro12345 初始时，变量 c 的地址为0。变量 c[a] 的地址为 0 + a = a。而 (&c[a])[b] 的地址为 a + b。虽然使用了巧妙的技巧，但仍然隐式地使用了 "add" 操作。 - Landys

请注意，您需要分配一个足够大的数组来存储最大的总和。否则，创建超出数组边界的指针将导致未定义行为。 - Nayuki

@Nayuki 这不是一个数组。 - wizzwizz4

Answer 3

没有 + 对吗？

int add(int a, int b) 
{
   return -(-a) - (-b);
}

- dfowler

---

在问题的评论中，@pomeranian.myopenid.com提到不能使用任何算术运算符。此外，最好将其写为a - (-b)，以使用减法作为替代操作。 - Lara Dougan

Answer 4

CMS的add()函数很优美。不应该被一元负号（非按位操作，相当于使用加法：-y == (~y)+1）所污染。因此，这里提供了一个使用相同的只使用位运算符的设计的减法函数：

int sub(int x, int y) {
    unsigned a, b;
    do {
        a = ~x & y;
        b =  x ^ y;
        x = b;
        y = a << 1;
    } while (a);
    return b;
}

- Deadcode

---

这并没有回答问题，问题要求进行加法而不是减法。 - MD XF

@MD XF，我正在回答用户23126在CMS的答案评论中提出的问题。正如我上面解释的那样，我认为CMS对这个评论的回答是不令人满意的，因为一元否定等同于使用加法。无法在评论中放置多行代码，因此我将其发布为答案。还请注意，用户23126是最初的问题提出者-因此，在某种程度上，这确实可以作为回答问题的资格。 - Deadcode

虽然问题确实是如何在不使用+运算符的情况下添加两个数字，但像其他人所说，使用 a - (-b) 很容易实现。因此，回答如何在不使用任何算术运算符的情况下进行操作更符合问题的本意。此外，User23126直接说明，即使它执行加法，“+”运算符以外的运算符也是不可接受的，“++”与否定背后的一部分非常相似。 - Deadcode

Answer 5

定义“最佳”。以下是Python版本：

len(range(x)+range(y))

+ 运算符执行的是列表连接，而不是加法运算。

- Charlie Martin

---

不使用加号操作符。 - MD XF

x = list(range(a)); x.extend(range(b)); len(x)x = list(range(a)) x.extend(range(b)) len(x) - Gaurav Jain

Answer 6

作弊。您可以将数字取反并从第一个数字中减去 :)

如果不行，可以查一下二进制加法器的工作原理 :)

编辑：我发布后看到了您的评论。

二进制加法的详细信息在这里。

- Andrew Rollings

---

二进制加法的URL已经失效。 - realPK

链接已经失效，答案的其余部分无效，应该被删除。 - MD XF

链接已经更正，答案与原问题的评论上下文相关。 - Andrew Rollings

Answer 7

注意，这是一个名为ripple-carry adder的加法器，它能够工作，但性能不是最优的。大多数硬件内置的二进制加法器都是一种快速加法器，例如carry-look-ahead adder。

如果将carry_in设置为0，则我的波动进位加法器适用于无符号整数和2的补码整数；如果将carry_in设置为1，则适用于1的补码整数。我还添加了标志以显示加法中的下溢或上溢。

#define BIT_LEN 32
#define ADD_OK 0
#define ADD_UNDERFLOW 1
#define ADD_OVERFLOW 2

int ripple_add(int a, int b, char carry_in, char* flags) {
    int result = 0;
    int current_bit_position = 0;
    char a_bit = 0, b_bit = 0, result_bit = 0;

    while ((a || b) && current_bit_position < BIT_LEN) {
        a_bit = a & 1;
        b_bit = b & 1;
        result_bit = (a_bit ^ b_bit ^ carry_in);
        result |= result_bit << current_bit_position++;
        carry_in = (a_bit & b_bit) | (a_bit & carry_in) | (b_bit & carry_in);
        a >>= 1;
        b >>= 1;
    }

    if (current_bit_position < BIT_LEN) {
        *flags = ADD_OK;
    }
    else if (a_bit & b_bit & ~result_bit) {
        *flags = ADD_UNDERFLOW;
    }
    else if (~a_bit & ~b_bit & result_bit) {
        *flags = ADD_OVERFLOW;
    }
    else {
        *flags = ADD_OK;
    }

    return result;
}

- doktaru

---

不幸的是，增量运算符（current_bit_position ++）需要加法。我知道这有点挑剔。 - user23126

@pomeranian.myopenid.com 是的，在这种情况下是正确的。在硬件中，每个位都有单独的逻辑门，而且不使用循环。如果展开此循环，则可以在不使用++运算符的情况下使用它。 - Lara Dougan

@Lara：是的，展开循环。对于32位，它将是while循环内代码的32个副本。这将提供一个漂亮的硬件伪代码和一个奖励点：它甚至可以执行！编程硬件遵循不同的规则，因此有些最佳实践在这里不适用... - nalply

Answer 8

基于Go语言的解决方案

func add(a int, b int) int {

for {
    carry := (a & b) << 1
    a = a ^ b
    b = carry 
    if b == 0 {
        break
    }
}

return a 

}

相同的解决方案可以用Python实现，但是在Python中有一些关于数字表示的问题，Python对于整数有超过32位的限制，因此我们需要使用掩码来获取最后32位。

例如：如果我们不使用掩码，我们将无法得到数字(-1,1)的结果。

def add(a,b):   
    mask = 0xffffffff

    while b & mask:
        carry = a & b
        a = a ^ b
        b = carry << 1

    return (a & mask)

- Prajilesh

---

最简单的方法是直接 return a&mask。检查是否需要复杂化代码只会让事情变得更麻烦，而且 & 运算是很便宜的。 - Peter Cordes

Answer 9

使用位运算符的Java解决方案：

// Recursive solution
public static int addR(int x, int y) {

    if (y == 0) return x;
    int sum = x ^ y; //SUM of two integer is X XOR Y
    int carry = (x & y) << 1;  //CARRY of two integer is X AND Y
    return addR(sum, carry);
}

//Iterative solution
public static int addI(int x, int y) {

    while (y != 0) {
        int carry = (x & y); //CARRY is AND of two bits
        x = x ^ y; //SUM of two bits is X XOR Y
        y = carry << 1; //shifts carry to 1 bit to calculate sum
    }
    return x;
}

- realPK

---

将public static从两个中移除，它也可以在C中工作。+1 - MD XF

这正是 CMS 的回答（目前被接受的答案），但使用了有意义的变量名，并在内联注释中进行了说明，而非在文本中（CMS 的答案缺少多年，但我在2016年7月添加了它）。尽管如此，因其清晰正确地解释了问题而受到了赞许。 - Peter Cordes

其实，更好的说法是xor是一种无进位加法。递归版本中的第一个注释表明它是两个整数的和，这是错误的。 - Peter Cordes

@PeterCordes 的答案包含了一个主方法和有效的 C 代码。我在此添加的仅为有效的 Java 方法。该代码已在我的本地机器上进行过测试，而非直接从其他来源复制粘贴。感谢您的评论。 - realPK

Answer 10

这是一个便携式的一行三元递归解决方案。

int add(int x, int y) {
    return y == 0 ? x : add(x ^ y, (x & y) << 1);
}

- Edward J Beckett