It is easy to multiply a bit string by : You just shift each digit positions to the left and fill the lower positions that have been freed with 0. Because we only consider bit strings of a fixed length , the most significant bit will be lost when shifting left by 1.
Dividing by powers of 2 works similarly. Instead of shifting left, we have to shift right. Here, the most significant positions are filled with zeros.
However, this does not preserve the sign under the signed interpretation if the bit string denotes a negative number. Consider the following example and let the length of the bit string be 4:
To remedy this problem, we introduce another right shift. The signed right shift does not fill in zeroes but replicates the most significant bit:
Show that the shift definitions are sound modulo . For the left shift, this means proving . Formulate respective criteria for the two right shifts and prove them as well.