Basics

Prev: Introduction

Next: Power-of-2 Boundaries

Sections

• 2-1 Manipulating Rightmost Bits
• 2-2 Addition Combined with Logical Operations
• 2-3 Inequalities among Logical and Arithmetic Expressions
• 2-4 Absolute Value Function
• 2-5 Average of Two Integers
• 2-6 Sign Extension
• 2-7 Shift Right Signed from Unsigned
• 2-8 Sign Function
• 2-9 Three-Valued Compare Function
• 2-10 Transfer of Sign Function
• 2-11 Decoding a “Zero Means $2^n$” Field
• 2-12 Comparison Predicates
• 2-13 Overflow Detection
• 2-14 Condition Code Result of Add, Subtract, and Multiply
• 2-15 Rotate Shifts
• 2-16 Double-Length Add/Subtract
• 2-17 Double-Length Shifts
• 2-18 Multibyte Add, Subtract, Absolute Value
• 2-19 Doz, Max, Min
• 2-20 Exchanging Registers
• 2-21 Alternating among Two or More Values
• 2-22 A Boolean Decomposition Formula
• 2-23 Implementing Instructions for all 16 Binary Boolean Operations

Problems

1. David de Kloet suggests the following code for the snoob function, for $x\ne 0$, where the final assignment to y is the result:

   This is essentially the same as Gosper’s code (page 15), except the right shift is done with a while loop rather than with a divide instruction. Because division is usually costly in time, this might be competitive with Gosper’s code if the while loop is not executed too many times. Let $n$ be the length of the bit strings $x$ and $y$, $k$ the number of 1-bits in the strings, and assume the code is executed for all values of $x$ that have exactly $k$ 1-bits. Then for each invocation of the function, how many times, on average, will the body of the while loop be executed?

2. The text mentions that a left shift by a variable amount is not right-to-left computable. Consider the function $x\ll (x\&1)$ [Knu8]. This is a left shift by a variable amount, but it can be computed by

   $x+(x\&1)\cdot x$, or

   $x+(x\&(-(x\&1)))$,

   which are all right-to-left computable operations. What is going on here? Can you think of another such function?

3. Derive Dietz’s formula for the average of two unsigned integers.

4. Give an overflow-free method for computing the average of four unsigned integers, $(a+b+c+d)/4$.

5. Many of the comparison predicates shown on page 23 can be simplified substantially if bit 31 of either $x$ or $y$ is known. Show how the seven-instruction expression on page 23 can be simplified to three basic RISC, non-comparison, instructions if $y_{31}=0$.

6. Show that if two numbers, possibly distinct, are added with end-around carry, the addition of the carry bit cannot generate another carry out of the high-order position.

7. Show how end-around carry can be used to do addition if negative numbers are represented in one’s-complement notation. What is the maximum number of bit positions that a carry, from any bit position, might be propagated through?

8. Show that the MUX operation, $(x\&m)\mid (y\&\sim m)$, can be done in three instructions on the basic RISC, which does not have the and-with-complement instruction.

9. Show how to implement $x\oplus y$ in four instructions with and-or-not logic.

Given a 32-bit word $x$ and two integer variables $i$ and $j$ in registers, show code to copy the bit of $x$ at position $i$ to position $j$. The values of $i$ and $j$ have no relation, but assume that $0\le i,j\le 31$.

How many binary Boolean instructions are sufficient to evaluate any $n$-variable Boolean function if it is decomposed recursively by the method of the theorem?

Show that alternative decompositions of Boolean functions of three variables are possible, including the negative Davio decomposition and a form involving $(z+h(x,y))$.

It is mentioned in the text that all 16 binary Boolean operations can be done with the eight instructions shown in Table 2-3, by interchanging the inputs or by having both register fields of the instruction refer to the same register. Show how to do this.

Suppose you are not concerned about the six Boolean functions that are really constants or unary functions, namely $f(x,y)=0,1,x,y,\sim x$, and $\sim y$, but you want your instruction set to compute the other ten functions with one instruction. Can this be done with fewer than eight binary Boolean instruction types, or opcodes?

Exercise 13 shows that eight instruction types suffice to compute any of the 16 two-operand Boolean operations with one R-R, register-register, instruction. Show that six instruction types suffice in the case of R-I, register-immediate, instructions. With R-I instructions, the input operands cannot be interchanged or equated, but the second input operand, the immediate field, can be complemented or, in fact, set to any value at no cost in execution time. Assume for simplicity that the immediate fields are the same length as the general purpose registers.

Show that not all Boolean functions of three variables can be implemented with three binary logical instructions.