Interview Question

Interview Santa Clara, CA

There are 8 bits inputs ,only use full adder to detect how

  many logic 1's

Interview Answer

2 Answers


first think of how many bits do you need to detect the number of logic 1s in an 8 bit input. highest number will be 8. so you need 4 bits to represent that. how can you compute this value though? the optimal way i think to do this problem is to look at the properties of a full adder. there are 3 inputs (A, B, and Cin) and 2 outputs (S and Cout). You can hook each input of a full adder to a bit value. Therefore, what you end up having is 3 full adders FA0 to compute b0(A) + b1(B) + b2(Cin), FA1 to compute b3(A) + b4(B) + b5(Cin), and FA2 to compute b6(A) + b7(B) + 0 (we dont have a 9th bit). Each FA therefore will produce a 2 bit added sum S1, S2, and S3. Now we need to add S1 and S2 together with 2 FAs, which is pretty straight forward, and get S12. Then we have to add S3 to S12 using 3 FAs because a 3 bit number + a 2 bit number can equal a 4 bit number. We therefore use 7 FAs. Usually, the question is calculate the number of 1s in a 7bit number, which actually reduces the number of FAs to 4. we keep S1 and S2, but don;t need FA3, because we can use bit7 as a Carry in for our computation.

moaxgeni on Sep 11, 2012

Are you not using a total of 8 FAs with your approach here? 3 + 2 + 3 = 8

Sri on Oct 15, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.