What is the minimum number of 2-to-1 muxes needed to implement a 129-to-1 mux?

I understand that if the requirement was to implement a mux that was a power of two there is the trick where you can do do x -1, so for instance if I wanted to implement a 8-to-1 mux, I would use 7 muxes because 8 = 23 and 23 - 1 = 7. But how does that change if you wanted to implemented a mux that is not a clean power of 2?

• 7× 2:1 mux have a total number of inputs that is 14. I'm surprised you can mux 128 inputs with that! Are you sure you've got that righ? – Marcus Müller Jan 27 at 16:12
• @MarcusMüller They're claiming an 8-to-1 mux with 7, not 128-to-one. – Hearth Jan 27 at 16:13
• @Hearth ah shoot, my mistake – Marcus Müller Jan 27 at 16:15

Add another 2:1 mux in front of your 128:1 mux; that gives you exactly 129 possible states, with the least additional components.

• So in total that is 8 muxes right? – PeraltaLearns Jan 27 at 16:11
• @PeraltaLearns You need a lot more than 7 2:1 muxes to get a 128:1 mux. – Hearth Jan 27 at 16:12
• 2^(7) = 128 - 1 = 127 muxes needed just to get a 128:1 mux. If I wanted the 129:1 mux in the question I would need and additional mux so 128 in total? – PeraltaLearns Jan 27 at 16:16
• @PeraltaLearns I think you can trust your own math well enough to not need our confirmation in this – Marcus Müller Jan 27 at 16:17
• If you don't trust yourself, draw the entire circuit on a napkin for 2, 4 and 8 inputs and see that the count matches a proposed math model. Then use that model for the large case. – Chris Stratton Jan 27 at 16:32

Ports MUXes (2:1) ...

N     X                 INT((Log(N)/LOG(2)+0.5) -1
0     0                    0
1     1                    1
2     1                    1
3     2                    2
4     2                    2
5     3                    3


Roundup (Log N / Log 2) = X = INT((Log(N)/LOG(2)+0.5) -1 for $$\2^X\$$

for N=129 X=8 (2:1 MUX's)