next up previous

Exercise 7: Bit shifts and mathematical operations.

(a) Prove that if is the n-bit representation of the integer x, then (a) shifting b left by i bits is equivalent to multiplying x by and (b) shifting b right by i bits is equivalent to dividing x by (ignoring any remainder).

(b) If , b represents a negative number in a two's complement system. In what is known as a ``logical shift right'' 0's are inserted into the leftmost bits, which means the result will be a positive number. Obviously if we divide a negative number by a power of two we expect a negative result, and in this case the logical shift doesn't give the correct answer. For example, . The 8-bit two's complement representation of -16 is 11110000. If we shift it right by two bits to divide by 4, we get 00111100, which represents 60, not -4. Can you think of a simple way to ``fix'' the shift operation so that it gives the correct result when it shifts both positive and negative numbers?