h1

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.

Advertisements

7 comments

  1. please send me the answer for this


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


  3. 4 full adders.
    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;
    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…


  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.



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: