COMP 273 Lecture Notes - Lecture 7: Finite-State Machine, Normalized Number, Floating Point
27 Feb 2016
School
Department
Course
Professor
Document Summary
Suppose we have two unsigned integers, a and b, and we wish to compute their product. Let a be the multiplicand and b the multiplier: For example, if we are multiplying two 32 bit unsigned integers, then we may need as many as 64 bits to represent the product. Recall your grade school algorithm for multiplying two numbers. We can use the same algorithm if the numbers are written in binary. The reason is that shifting a binary number one bit to the left is the same as multiplying by 2, just as decimal multiplication by ten shifts digits left by one. In the case of binary, each 1 bit bi in the multiplier means we have a contribution 2i times the multiplicand, and so we add the shifted multiplicands. In the grade school algorithm, we compute all the left shifts in advance, building up several rows of numbers which correspond to the digits of the multiplier.
