# Nt1310 Unit 2 Essay

9623 Words39 Pages
C HA PT ER 2 BASICS 2–1 Manipulating Rightmost Bits Some of the formulas in this section find application in later chapters. Use the following formula to turn off the rightmost 1-bit in a word, producing 0 if none (e.g., 01011000 ⇒ 01010000): x & (x – 1) This may be used to determine if an unsigned integer is a power of 2; apply the formula followed by a 0-test on the result. Similarly, the following formula can be used to test if an unsigned integer is of the form 2 n – 1 (including 0 or all 1’s): x & (x + 1) Use the following formula to isolate the rightmost 1-bit, producing 0 if none (e.g., 01011000 ⇒ 00001000): x & (– x) Use the following formula to isolate the rightmost 0-bit, producing 0 if none (e.g., 10100111 ⇒ 00001000): ¬x &…show more content…
These formulas all have duals in the following sense. Read what the formula does, interchanging 1’s and 0’s in the description. Then, in the formula, replace x – 1 with x + 1 , x + 1 with x – 1 , – x with ¬( x + 1 ) , & with |, and | with &. Leave x and ¬ x alone. Then the result is a valid description and formula. For example, the dual of the first formula in this section reads as follows: Use the following formula to turn on the rightmost 0-bit in a word, producing all 1’s if none (e.g., 10100111 ⇒ 10101111): x | (x + 1) There is a simple test to determine whether or not a given function can be implemented with a sequence of add’s, subtract’s, and’s, or’s, and not’s [War]. We may, of course, expand the list with other instructions that can be composed from…show more content…
Below we show branch-free expressions to evaluate the result into the sign position. To produce the 1/0 value used by some languages (e.g., C), follow the code with a shift right of 31. To produce the – 1 ⁄ 0 result used by some other languages (e.g., Basic), follow the code with a shift right signed of 31. These formulas are, of course, not of interest on machines such as MIPS, the Compaq Alpha, and our model RISC, which have comparison instructions that compute many of these predicates directly, placing a 0/1-valued result in a general purpose register. A machine instruction that computes the negative of the absolute value is handy here. We show this function as “nabs.” Unlike absolute value, it is well defined in that it never overflows. Machines that do not have “nabs” but have the more usual “abs” may use – abs(x) for nabs(x). If x is the maximum negative number, this overflows twice, but the result is correct. (We assume that the absolute value and the negation of the maximum negative number is itself.) Because some machines have neither “abs” nor “nabs,” we give an alternative that does not use them. The “nlz” function is the number of leading 0’s in its argument. The “doz” function (difference or zero) is described on page