New answers tagged

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 ...
Steven's user avatar
  • 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 ...
gnasher729's user avatar
  • 28.4k

Top 50 recent answers are included