Bitwise Multiplication with Shifts and Adds

I’ve been learning some x86 assembly over the past week.

Something that assembly language does really well (even better than a higher level language such as C) is bit manipulation. For example, here is a way to multiply two 32 bit unsigned integers using only shifts and adds. This is an interesting exercise because shifts and adds are among the most low-level operations a CPU can perform, and it seems likely that the MUL instruction is in practice implemented using some combination of shifts and adds.

To see how this is possible, we first realise that any number can be written as a sum of powers of 2:

E.g.

Due to the distributive property of multiplication, when we multiply a number, we can multiply by the powers of two and sum:

And in binary, multiplying by a power of two is simply a bit-shift to the left:

So for each power of two of 42, we can multiply by shifting 20 by the required number of bits and accumulating the result:

Here is the listing in MASM. The actual multiplication loop is just 5 lines of code.

; Binary Multiplication
.code
main PROC
	mov		eax,42
	mov		ebx,20
	call	bitmul
						; EAX = 840
	exit
main ENDP


; Multiplies an unsigned 32 bit integer in EAX by EBX
; Receives: EAX = uint32, EBX = uint32
; Returns: EAX
bitmul PROC
	push	edx			; save used registers
	push	ecx
	mov		edx, eax	; store original multiplicand into EDX
	mov		ecx, 32		; loop for 32 bits
	mov		eax, 0		; eax will accumulate the result

BeginLoop:
	shr		edx, 1		; shift lowest bit into carry flag
	jnc		DontAdd		; jump if carry flag not set
	add		eax, ebx
DontAdd:
	shl		ebx, 1		; shifting multiplies EBX by 2
	loop	BeginLoop

	pop		ecx			; restore used registers
	pop		edx
	ret
bitmul ENDP

END main