Binary multiplication
= Binary multiplication
{title2=$XY=\sum_i y_i2^iX$}
For nonnegative integers with <binary representation> $Y=\sum_{i=0}^{w-1}y_i2^i$, multiply by $X$ by summing the shifted terms $y_i2^iX$. Each term is either zero or a <left bit shift> of $X$. An unsigned $w$-<bit> input pair needs at most $2w$ product <bits>, because $(2^w-1)^2<2^{2w}$. This expansion follows from distributivity and motivates a <binary multiplier>.