2

Suppose I have a black box with 3 inputs (each input is 1 bit) and 2 bits output. The black box counts the amount of turned on input bits. Using only such black boxes,one needs to implement the counter of turned on bits in the input,which has 7 bits.The implementation should use the minimum possible amount of black boxes.

//This is a job interview question

4

2 回答 2

6

你正在做一个二进制加法器。试试这个......
两个黑框输入，剩下一个输入：

 7 6 5      4 3 2      1
 | | |      | | |      | 
-------    -------     |
|     |    |     |     |
| H L |    | H L |     |
-------    -------     |
  | |        | |       |

取两个低输出和剩余的输入 (1) 并将它们馈送到另一个黑盒：

            L L 1
            | | |
           -------
           |     |
           | C L |
           -------
             | |

这个黑盒的低输出将是结果的低位。高输出是进位位。将此进位位与前两个黑盒中的高位一起输入第四个黑盒：

 H H C   L
 | | |   |
-------  |
|     |  |
| H M |  |
-------  |
  | |    |

结果应该是输入中的“on”位数，以二进制表示，由高位、中位和低位表示。

于 2013-09-01T15:26:02.570 回答
3

假设每个 BB 输出一个 2 位二进制计数 00、01、10 或 11，当其输入中的 0、1、2 或 3 个打开时。还假设所需的最终输出 O₄O2O₁ 是 3 位二进制计数 000 ... 111，当 7 个输入位 i₁...i₇ 中的 0、1、...7 位打开时。对于一般这样的问题，您可以为 BB 所做的事情编写一个布尔表达式，为所需的输出编写一个布尔表达式，然后合成输出。然而，在这种特殊情况下，尝试将 i1、i2、i3 放入第一个框 B1，将 i₄、i5、i6 放入第二个框 B2，将 i7 放入第三个框 B3 的一个输入的明显方法。看这个很明显，如果您将 B1 和 B2 的单位输出运行到 B3 的其他两个输入中，则 B3 的单位输出等于所需的值 O1。您可以通过框 B₄ 获得 B₁、B₂、B₃ 的两个输出之和，

于 2013-09-01T15:27:55.670 回答