turned on bits counter

Question

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

Answer 1

You're making a binary adder. Try this...
Two black boxes for input with one input remaining:

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

Take the two low outputs and the remaining input (1) and feed them to another black box:

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

The low output from this black box will be the low bit of the result. The high output is the carry bit. Feed this carry bit along with the high bits from the first two black boxes into the fourth black box:

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

The result should be the number of "on" bits in the input expressed in binary by the High, Middle and Low bits.