binary - 仅使用位逻辑查找二进制中两个整数的最大值

Question

这有点棘手，我认为这对于那些能够胜任这项任务的人来说是一个很好的挑战。我确实搜索了之前提出的所有问题，但找不到我想要的。

这里的目标是，给定 2 个整数，在 n 位上用二进制编写，仅使用逻辑运算找到其中最大的一个(AND, OR, ...) 对每个整数的 n 位进行运算(如果第一个整数最大，则结果为 0，否则为 1)。最终，我们的目标是能够绘制一个电子电路，其中 2*n 位将是有或没有张力的电线，并将电线插入到执行逻辑运算的实际电子元件中。

我开始思考这个问题，意识到无论发生什么(即无论 n 是什么)，2^n 都大于 2^0 + ... + 2^(n-1) (从数学上来说，这很容易得出和)。这意味着，当另一个整数中的相应位为 0 且 n 和 k 之间的所有其他位(k 左边的所有位)相同时，无论哪个整数有一个位(例如数字 k)为 1，该位都是最大的。示例:

A:010(1)1011 大于B : 010(0)1111，有效位位于括号内。它左边的所有位都是相同的，我们不必关心其他位。

因此，可以对所有位对执行异或 (XOR) 操作:有效位将产生 1，然后我可以在 A 的相应位与该 XOR 的结果之间执行 NAND，这样就可以了如果 A 的第 k 位是 1，则 d 产生 0；如果 B 的第 k 位是 1，则 d 产生 1。唯一的问题是……有效位右侧的位怎么样？它们可以不同(因此在执行 XOR 时也会产生 1)，但我必须忽略这一点......有什么想法吗？

Answer 1

您关心硬件实现，所以我想您最好将 A 和 B 视为有符号的 N 位整数，然后

1. 将 B 反转为其 -B 表示形式；
2. 使用 N 位将 A 与 B 相加 Full Adder ;
3. 使用结果的符号作为 2 输入、N 位多路复用器的选择器变量。

当然，它只能用逻辑函数来表达。

更详细地讨论第三点，只需检查符号S(1:负，0:正)是否满足谓词B>A。因此，如果多路复用器针对选择器值 0 获取的输入是 A(对于选择器值 1 来说是 B)，您就会得到结果。在相等的情况下，您仍然选择 A，但是 A=B，因此这在逻辑上与您选择哪一个无关。

作为 A 和 B 变量，这是最明智的方法，因为您可以重用加法器进行加法。我想，针对检查最大值的特定情况进行优化肯定是可能的。

附加评论:

需要强调的是，逐步检查 A 和 B 的每个数字的顺序实现在最坏的情况下需要 N > 检查返回结果。如果您有 A 和 B 两个值流，则必须保证能够跟上它们。因此， max() 函数的逻辑工作频率是数据流频率的 N 倍。从另一个角度来看，您需要减慢将数据输入 max() 逻辑的速度。

相反，我建议的组合实现(或其任何优化)以硬件资源来交换速度。换句话说，它的速度与您为 A 和 B 生成数据的速度一样快。与顺序实现相比，组合实现的传播延迟通常也更高，但这不是频率问题。