1-1 Notation

This book distinguishes between mathematical expressions of ordinary arithmetic and those that describe the operation of a computer. In "computer arithmetic," operands are bit strings, or bit vectors, of some definite fixed length. Expressions in computer arithmetic are similar to those of ordinary arithmetic, but the variables denote the contents of computer registers. The value of a computer arithmetic expression is simply a string of bits with no particular interpretation. An operator, however, interprets its operands in some particular way. For example, a comparison operator might interpret its operands as signed binary integers or as unsigned binary integers; our computer arithmetic notation uses distinct symbols to make the type of comparison clear.

The main difference between computer arithmetic and ordinary arithmetic is that in computer arithmetic, the results of addition, subtraction, and multiplication are reduced modulo 2n, where n is the word size of the machine. Another difference is that computer arithmetic includes a large number of operations. In addition to the four basic arithmetic operations, computer arithmetic includes logical and, exclusive or, compare, shift left, and so on.

Unless specified otherwise, the word size is 32 bits, and signed integers are represented in two's-complement form.

Expressions of computer arithmetic are written similarly to those of ordinary arithmetic, except that the variables that denote the contents of computer registers are in bold-face type. This convention is commonly used in vector algebra. We regard a computer word as a vector of single bits. Constants also appear in bold-face type when they denote the contents of a computer register. (This has no analogy with vector algebra because in vector algebra the only way to write a constant is to display the vector's components.) When a constant denotes part of an instruction, such as the immediate field of a shift instruction, light-face type is used.

If an operator such as "+" has bold-face operands, then that operator denotes the computer's addition operation ("vector addition"). If the operands are light-faced, then the operator denotes the ordinary scalar arithmetic operation. We use a light-faced variable x to denote the arithmetic value of a bold-faced variable x under an interpretation (signed or unsigned) that should be clear from the context. Thus, if x = 0x80000000 and y = 0x80000000, then, under signed integer interpretation, x = y = -231, x + y = -232, and x + y = 0. Here, 0x80000000 is hexadecimal notation for a bit string consisting of a 1-bit followed by 31 0-bits.

Bits are numbered from the right, with the rightmost (least significant) bit being bit 0. The terms "bits," "nibbles," "bytes," "halfwords," "words," and "doublewords" refer to lengths of 1, 4, 8, 16, 32, and 64 bits, respectively.

Short and simple sections of code are written in computer algebra, using its assignment operator (left arrow) and occasionally an if statement. In this role, computer algebra is serving as little more than a machine-independent way of writing assembly language code.

Longer or more complex computer programs are written in the C++ programming language. None of the object-oriented features of C++ are used; the programs are basically in C with comments in C++ style. When the distinction is unimportant, the language is referred to simply as "C."

A complete description of C would be out of place in this book, but Table 1-1 contains a brief summary of most of the elements of C [H&S] that are used herein. This is provided for the benefit of the reader who is familiar with some procedural programming language but not with C. Table 1-1 also shows the operators of our computer-algebraic arithmetic language. Operators are listed from highest precedence (tightest binding) to lowest. In the Precedence column, L means left-associative; that is,



and R means right-associative. Our computer-algebraic notation follows C in precedence and associativity.

In addition to the notations described in Table 1-1, those of Boolean algebra and of standard mathematics are used, with explanations where necessary.

Table 1-1. Expressions of C and Computer Algebra



Computer Algebra




0x? 0b?/span>

Hexadecimal, binary constants




Selecting the kth component



x0, x1, ?/span>

Different variables, or bit selection (clarified in text)



f(x, ?

Function evaluation




Absolute value (but abs(-231) = -231)




Negative of the absolute value


x++, x--


Postincrement, decrement


++x, --x


Preincrement, decrement


(type name)x


Type conversion

14 R



x to the kth power



?span class=docemphbolditalic1>x, x?/span>

Bitwise not (one's-complement)




Logical not (if x = 0 then 1 else 0)




Arithmetic negation

13 L


x * y

Multiplication, modulo word size

13 L


x ?y

Signed integer division

13 L




Unsigned integer division

13 L


rem(x, y)

Remainder (may be negative), of (x ?y) signed arguments

13 L


rem(x, y)

Remainder of graphics/icon03.gifunsigned arguments



mod(x, y)

x reduced modulo y to the interval [0, abs(y) - 1]; signed arguments

12 L

x + y, x - y

x + y, x - y

Addition, subtraction

11 L

x << y, x >> y


Shift left, right with 0-fill ("logical" shifts)

11 L

x >> y


Shift right with sign-fill ("arithmetic" or "algebraic" shift)

11 L



Rotate shift left, right

10 L

x < y, x <= y,

x > y, x >= y

x < y, x y,

x > y, x y,

Signed comparison

10 L

x < y, x <= y,

x > y, x >= y



Unsigned comparison

9 L

x == y, x != y

x = y, x y

Equality, inequality

8 L

x & y

x & y

Bitwise and

7 L

x ^ y

x y

Bitwise exclusive or

7 L


x y

Bitwise equivalence (?x y))

6 L

x | y

x | y

Bitwise or

5 L

x && y


Conditional and (if x = 0 then 0 else if y = 0 then 0 else 1)

4 L

x || y


Conditional or (if x 0 then 1 else if y 0 then 1 else 0)

3 L


x || y


2 R

x = y

x y


Our computer algebra uses other functions, in addition to "abs," "rem," and so on. These are defined where introduced.

In C, the expression x < y < z means to evaluate x < y to a 0/1-valued result, and then compare that result to z. In computer algebra, the expression x < y < z means (x < y) & (y < z).

C has three loop control statements: while, do, and for. The while statement is written:

while (expression) statement

First, expression is evaluated. If true (nonzero), statement is executed and control returns to evaluate expression again. If expression is false (0), the while-loop terminates.

The do statement is similar, except the test is at the bottom of the loop. It is written:

do statement while (expression)

First, statement is executed, and then expression is evaluated. If true, the process is repeated, and if false, the loop terminates.

The for statement is written:

for (e1; e2; e3) statement

First, e1, usually an assignment statement, is executed. Then e2, usually a comparison, is evaluated. If false, the for-loop terminates. If true, statement is executed. Finally, e3, usually an assignment statement, is executed, and control returns to evaluate e2 again. Thus, the familiar "do i = 1 to n" is written:

for (i = 1; i <= n; i++) 

(This is one of the few contexts in which we use the postincrement operator.)