Answers to selected exercises
CHAPTER 2, EXERCISE 12. (i) Let m = a0 + 2a1 + … + 2d−1ad−1. Numbering the first row as zero, the two entries in the ith row are ai + 2ai+1 + … + 2d−1−iad−1 and 2in. The first of these is odd if and only if ai = 1; so we add the values 2in for which ai = 1, that is, we calculate ai2in = mn.
(ii) If n is written in base 2, then doubling has the effect of shifting it one place to the left; so the terms added are exactly those occurring in the standard long multiplication done in base 2.
(iii) With these modifications, we replace 2in by , so that the final result ...