我对使用循环或位移和添加移位位组合的算法实现加法、用乘法实现乘法或用乘方、对数等高级运算实现乘方等著名问题已经很熟悉了。
现在,我想知道是否有任何方法可以仅使用高级运算(例如乘法、乘方、对数等)来实现加法,而不包括减法。
这是否可以通过一些算法结合这些运算(可能包括比特运算符作为辅助)来实现,或者是加法作为公理所服务的基本运算,因此除了其定义外,无法通过其他方式再现?
谢谢。
我对使用循环或位移和添加移位位组合的算法实现加法、用乘法实现乘法或用乘方、对数等高级运算实现乘方等著名问题已经很熟悉了。
现在,我想知道是否有任何方法可以仅使用高级运算(例如乘法、乘方、对数等)来实现加法,而不包括减法。
这是否可以通过一些算法结合这些运算(可能包括比特运算符作为辅助)来实现,或者是加法作为公理所服务的基本运算,因此除了其定义外,无法通过其他方式再现?
谢谢。
当然可以:
编辑:从更为推测性的角度来看,你应该期望能够通过更高级别的操作执行低级别的操作。只要更高级别的操作是由低级别的操作构建起来的,这些操作就应该至少能够执行它们的基础操作。但可能不是一种简单和直接的方式,见下面的评论。一个人可以告诉你1+1=2,但询问计算机或甚至更简单的设备会更便宜、更安全。
ln
和exp
本身只存在于数学中,在实践中只能存在近似值,否则结果有无限多位二进制数字,永远无法得出。因此,我希望用有限环/域或BigInt及其对应的有理数来解决这个问题。 - harold如果您想要严格一点,两个二进制数字可以使用位运算符OR,XOR和AND相加,而不是严格“添加”任何东西。对于和a + b = c,第n位可以像这样计算:
cn = an XOR bn XOR 进位
进位 = (an AND bn) OR ((an XOR bn) 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;
}
+
时计算机实际执行的操作。) - גלעד ברקןc |= (an ^ bn ^ carry) * mask
有一个真正的乘法,尽管你可以写成 if (an ^ bn ^ carry) c |= mask
。 (你也可以认为 |=
实际上是一个和,可以写成 +=
,这也是有道理的。) - m69 ''snarky and unwelcoming''