如何在算术电路中构建比较运算符(comparator)

How to build a comparison operator (comparitor) in an arithmetic circuit

我正在尝试将基本程序转换为算术电路。我坚持将大于运算符转换为算术电路的步骤。具体来说,我不知道如何将以下内容转换为算术电路(其中输入x,y):

if x >= y: return 1 else: return 0

为了清楚起见,我需要能够用算术电路来表达这一点。这意味着我需要能够仅使用数字的加法和乘法来计算它(在 Z_p 中)。

我一直在整个 Web 上搜索解决方案,但我找到的所有内容都告诉我如何使用布尔电路执行此操作。我知道我可以将数字转换成它们的位字符串并执行这种布尔方式。我想知道任何替代方法来做到这一点。这个节目可以只用加法和乘法,但我不知道怎么做。

如果您对数据使用正确的编码,则不需要任何电路。最好和最广泛用于编码有符号整数的是 two's complement.
正数由二进制代码编码,负数 A<0;通过考虑 2^n-|A|=2^n+A 呈现为正数,其中 n 是代码的位数。

补码有(至少)两个主要优点。
第一个是它在很大程度上简化了算术运算。例如,负数 A 由 2^n+A 进行算术编码,因此不必关心操作数的符号,前提是忽略超过 2^n 的位,并且添加有符号数与添加无符号数相同。

第二个优点是正数在 0..2^(n-1)-1 范围内并且始终未设置其最高有效位。负数在 -1..-2^(n-1) 范围内。一旦添加到 2^n,它们的代码范围就是 2^(n-1)..2^n-1 并且对应于设置了最高有效位的数字。所以,要知道一个数字是否>=0,只需要测试它的最高有效位。

所以没有真正的 "circuit" 或算术运算符可以做到这一点。在程序中,这可以通过使用 MSB 计算 "and" 来完成。

int is_positive(int x) { return (x & (1<<31)) == 0 ); }

没有与、或或比较,只用算术运算是无法表达的。而且你必须有一种方法来检测一个数字是否完全为 0,这需要逻辑门。