Binary multiplication ($XY={\sum }_i{y}_i{2}^{i}X$)

For nonnegative integers with binary representation $Y={\sum }_{i=0}^{w-1}{y}_i{2}^i$, multiply by $X$ by summing the shifted terms $y_i{2}^{i}X$. 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.