CSE 326, Spring 1995: Homework 3

Due 4/19/95

1. (10 points) Consider a binary counter with b bits and the operation "increment" which adds one to the counter. Suppose the counter contains 010111 in binary for example. Incrementing the counter would result in 011000. In this case exactly 4 bits are touched. If the counter with 011000 is incremented then only one bit is touched. Show that if the counter is incremented from zero to n where n < 2^b, that only O(n) bits are touched. Hint: Bit i is touched on an increment only when the i-1 lower order bits are all ones. Examples for i = 4; for 010111 and 011111 the 4th bit is touched when the counter is incremented.
2. (10 points) 2.6 (a) (4), (5), and (6)
3. (10 points) Consider the recursive powering program on page 47. Convert the program into an iterative program which does not use recursion.