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 2ⁿ, 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 = -2³¹, x + y = -2³², 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
Precedence	C	Computer Algebra	Description
	0x?/p>	0x? 0b?/span>	Hexadecimal, binary constants
16	a[k]		Selecting the kth component
16		x0, x1, ?/span>	Different variables, or bit selection (clarified in text)
16	f(x,?tt>)	f(x, ?	Function evaluation
16		abs(x)	Absolute value (but abs(-2^31) = -2^31)
16		nabs(x)	Negative of the absolute value
15	x++, x--		Postincrement, decrement
14	++x, --x		Preincrement, decrement
14	(type name)x		Type conversion
14 R		x^k	x to the kth power
14	~x	?span class=docemphbolditalic1>x, x?/span>	Bitwise not (one's-complement)
14	!x		Logical not (if x = 0 then 1 else 0)
14	-x	-x	Arithmetic negation
13 L	x*y	x * y	Multiplication, modulo word size
13 L	x/y	x ?y	Signed integer division
13 L	x/y		Unsigned integer division
13 L	x%y	rem(x, y)	Remainder (may be negative), of (x ?y) signed arguments
13 L	x%y	rem(x, y)	Remainder of unsigned 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	Concatenation
2 R	x = y	x y	Assignment

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 (e₁; e₂; e₃) statement

First, e₁, usually an assignment statement, is executed. Then e₂, usually a comparison, is evaluated. If false, the for-loop terminates. If true, statement is executed. Finally, e₃, usually an assignment statement, is executed, and control returns to evaluate e₂ 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.)