## Puzzle #2

May 19, 2007OK, 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.

please send me the answer for this

by cheers January 5, 2008 at 5:01 pmgot a solution .. requeires 4 full adders .. if anyone has better .. buzz me ..

by Vamsi May 7, 2008 at 11:58 amVamsi

BITS Goa

INDIA

bunnynu@gmail.com

4 full adders.

by Troy October 14, 2009 at 10:04 pmbit 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;

c1,c2,c3 into adder4, get s4,c4;

c4s4s3 is the final answer.

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…

by srini January 28, 2010 at 11:22 amhow many input vectors of 7 bits one should check,in order to be sure that the designed system works correctly?

by Krol April 22, 2011 at 5:05 pmWat was the thought process behind this solution?

by Sai January 9, 2014 at 12:21 pmHow 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.

by Alex September 5, 2014 at 5:48 am