next up previous

Exercise 8: Low order bits and division by powers of 2.

Prove that if is the n-bit representation of the integer x, the low order i bits are the value of the remainder of . NOTE: this operation is also performed very efficiently on most machines. Let m be a pattern known as a ``mask'' that contains 0's in the high order n - i bits and 1's in the low order i bits. An operation known as a ``bitwise AND'' will compute a pattern x such that (the operation is the logical AND, which is 1 if and only if both operands are 1). To find the remainder of a division by , create a mask with i 1's in the low order bits, then ``and'' it with b. For example, the remainder of 14 (00001110 in an 8-bit system) divided by is .