# CSE 326, Spring 1995: Homework 3

##
Due 4/19/95

- (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.
- (10 points)
2.6 (a) (4), (5), and (6)
- (10 points)
Consider the recursive powering program on page 47. Convert the program
into an iterative program which does not use recursion.