使用乘法实现加法

Question

我对使用循环或位移和添加移位位组合的算法实现加法、用乘法实现乘法或用乘方、对数等高级运算实现乘方等著名问题已经很熟悉了。

现在，我想知道是否有任何方法可以仅使用高级运算（例如乘法、乘方、对数等）来实现加法，而不包括减法。

这是否可以通过一些算法结合这些运算（可能包括比特运算符作为辅助）来实现，或者是加法作为公理所服务的基本运算，因此除了其定义外，无法通过其他方式再现？

谢谢。

- Uriel

---

这是一个数学问题，与编程无关。 - nwellnhof

阅读关于柯西乘积的内容，也许你会得到一些提示。 - Monah

我不是数学家，但我不知道有这样的事情。 - duffymo

如果一个人编写程序时不使用加/减等操作符，而是使用一些数据结构，比如集合、映射、向量、列表等，这样做是否可行？ - shole

投票关闭，因为这不是一个实际的编程问题。 - ivan_pozdeev

Answer 1

当然可以：

编辑：从更为推测性的角度来看，你应该期望能够通过更高级别的操作执行低级别的操作。只要更高级别的操作是由低级别的操作构建起来的，这些操作就应该至少能够执行它们的基础操作。但可能不是一种简单和直接的方式，见下面的评论。一个人可以告诉你1+1=2，但询问计算机或甚至更简单的设备会更便宜、更安全。

- Mats Lind

---

请注意，在实际系统中使用时可能会存在溢出和不准确结果的风险。 - Leon

如果我们想使用实际可实现的操作，是否仍然可以做到？ - harold

当然，ln()和exp()可以像ln(exp(a)*exp(b))一样实现，但是如果你的意思是“不使用加法就能实现”，那么我们基本上是在谈论如何在不执行加法的情况下执行加法。这应该非常困难。 - Mats Lind

我指的“可实现”是指在计算机上实现。ln和exp本身只存在于数学中，在实践中只能存在近似值，否则结果有无限多位二进制数字，永远无法得出。因此，我希望用有限环/域或BigInt及其对应的有理数来解决这个问题。 - harold

Answer 2

如果您想要严格一点，两个二进制数字可以使用位运算符OR，XOR和AND相加，而不是严格“添加”任何东西。对于和a + b = c，第n位可以像这样计算：

c_n = a_n XOR b_n XOR 进位
进位 = (a_n AND b_n) OR ((a_n XOR b_n) AND 进位)

当迭代比特时，应避免使用n++，并添加一些乘法以提高准确性：

int add(int a, int b) {
    int c = 0;
    char carry = 0;
    for (int mask = 1; mask; mask *= 2) {
        char an = a & mask ? 1 : 0;
        char bn = b & mask ? 1 : 0;
        c |= (an ^ bn ^ carry) * mask;
        carry = an & bn | (an ^ bn) & carry;
    }
    return c;
}

- m69 ''snarky and unwelcoming''

---

这还不够严谨。请定义"strictly adding"。（就我所知，您用位运算描述的实际上更接近于我们按下+时计算机实际执行的操作。） - גלעד ברקן

这是对“使用乘法”这一概念的固执解释，仅限于高级操作，比如特定的乘法运算，或者超越数学中的运算。 - greybeard

@greybeard 我对“一些结合这些操作的算法（可能还包括按位操作符）”这句话理解得非常字面化 :-) - m69 ''snarky and unwelcoming''

@UrielEli 好的，c |= (an ^ bn ^ carry) * mask 有一个真正的乘法，尽管你可以写成 if (an ^ bn ^ carry) c |= mask。 （你也可以认为 |= 实际上是一个和，可以写成 +=，这也是有道理的。） - m69 ''snarky and unwelcoming''