5

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

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

我开始思考这个问题，意识到无论发生什么（即无论 n 是什么），2^n 都大于 2^0 + ... + 2^(n-1) （从数学上讲，这很容易提出）。这意味着当另一个整数中的相应位为 0 时，任何一个整数的位（比如数字 k）为 1，并且 n 和 k 之间的所有其他位（k 左侧的所有位）相同，都是最大的。例子 ：

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

因此，可以对所有位对执行异或（XOR）：重要的位会产生 1，然后我可以在 A 的相应位与 XOR 的结果之间执行 NAND，这样它就会产生如果 A 的第 k 位为 1，则为 0，如果 B 的第 k 位为 1，则为 1。唯一的问题是……重要的位右侧的位呢？它们可以不同（因此在执行 XOR 时也会产生 1）但我必须忽略这一点......有什么想法吗？

4

5 回答 5

2

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

  1. 反转B为其-B表示；
  2. A用BN 位全加器求和；
  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。与顺序实现相比，组合实现的传播延迟通常也更高，但这在频率方面不是问题。

于 2012-05-26T15:47:27.487 回答
1

两个整数中的较大者：

unsigned int a, b, max;
max = ((~(a >= b)+1) & a) | ((~(b >= a)+1) & b);

说明：假设一个整数是 4 个字节。(a >= b) 转换为 0001 或 0000。对于 (b >= a) 也是如此。在否定 "~X + 1" 后加 1 给出二进制补码。这样，比较中的 1 将转换为 FFFF。0 仍然是 0000。如果 a = b 我们有： FFFF & a | FFFF & b = a。如果 a > b 我们有： FFFF & a | 0000 & b = a。如果 b > a 我们有： 0000 & a | FFFF & b = b。

于 2015-04-11T18:02:11.940 回答
0

我将通过向二进制 AND 的第二个运算符添加一个数字来迭代这两个数字（我们称它们为 a和b ），直到其中一个数字变为 0...

如果其中一个数字是 0，另一个是 > 0，那么您将拥有两者中的最大值...

第一个循环：

a & 1 b & 1

第二个循环：

a & 10 b & 10

第三个循环：

a & 100 b & 100

等等...

要在操作后检查其中一个数字是否等于零，您可以（给定 n，已知数字的长度）在最重要的 n+1 位置使用 n 乘以零加 1 的数字生成一个和。 ..

我的 2 分（也许是错的）美分 :)

于 2012-05-26T15:36:22.127 回答
0 
A : 010(1)1011 
B : 010(0)1111

第一位移位

C : 0
D : 0

如果他们匹配下一个班次，如果他们不匹配返回D。

于 2014-05-05T22:53:50.737 回答
0

有些 IC 可以满足您的需求，例如 cmos 4063。该 IC 只能比较 4 位的数量，但它提供了通过级联多个设备进行扩展的可能性。

如果您感兴趣的是自己实现它的逻辑，您可以查看数据表http://www.intersil.com/content/dam/Intersil/documents/fn33/fn3318.pdf，其中包含逻辑图比较器的

于 2012-06-06T09:34:47.083 回答