## Puzzle #2

May 19, 2007

OK, here is another nice puzzle, which actually has applications in real life!
This one was given to me on the same IBM interview sometime around 10 years ago.

Here goes.

Again we are dealing with the poor engineers in the land of Logicia. For some sort of fancy circuitry, a 7-bit binary input is received. As a result it should give the amount of “1”s present in this vector. For example, for the inputs 1100110 and 1001110 the result should be the same and equal to 100 (4 in binary). This time however, the only components they have on their hands are Full Adders. Describe the circuit with minimum amount of parts.

This puzzle is fairly easy, and as I mentioned before has found some practical uses in some of my designs. More on this when I’ll give the answer.

2. got a solution .. requeires 4 full adders .. if anyone has better .. buzz me ..
Vamsi
BITS Goa
INDIA
bunnynu@gmail.com

bit 1,2,3 into adder1, get s1,c1;
bit 4,5,6 into adder2, get s2,c2;
bit 4,s1,s2 into adder3, get s3,c3;

• Its the description of parallel counters widely used in tree multipliers….and the counter described by u folks is called successive doubling counter…It is a relatively slow design…

4. how many input vectors of 7 bits one should check,in order to be sure that the designed system works correctly?

5. Wat was the thought process behind this solution?
How did u come up with this solution, please explain.

• Each full adder with inputs {a_n, b_n, ci_n} gives an output {co_n, s_n} which is the number of 1’s in the input, in binary. Think of s_n as indicating that there is one 1 in the input, and co_n as indicating that there are two 1’s in the input.

Now, if we sum s_n’s, we will get an answer that indicates the number of 1’s in those sums. This answer can go in the final answer in the LSB.

If we sum co_n’s, we will get an answer that indicates 2x the number of 1’s. This answer can go in the final answer, shifted left by 1 bit, to account for the 2x multiplier.