New answers tagged circuits
2
votes
Can you compute a majority function of n-bits using an O(n) size circuit?
Interpret each input as a 1-bit number, and sum all the inputs in a binary-tree fashion.
At the $i$-th level of the tree you're dealing with numbers with at most $i+1$ bits.
Hence the number of gates ...
- 28.3k
0
votes
3 bit binary multiplier?
For an n-bit by n-bit multiplier you use $n^2$ ANDs which each give a single bit in some bit position. For example in a 64 bit multiplier $x_{52} and $y_{22} would be a bit in position 74.
You arrange ...
- 28.4k
Top 50 recent answers are included