 # Hacker's Delight: The Basics

• Print
This chapter is from the book

## 2–3 Inequalities among Logical and Arithmetic Expressions

Inequalities among binary logical expressions whose values are interpreted as unsigned integers are nearly trivial to derive. Here are two examples: These can be derived from a list of all binary logical operations, shown in Table 2–1.

#### Table 2-1. The 16 Binary Logical Operations

Let f(x, y) and g(x, y) represent two columns in Table 2–1. If for each row in which f(x,y) is 1, g(x,y) also is 1, then for all (x,y), f(x, y) g(x, y). Clearly, this extends to word-parallel logical operations. One can easily read off such relations (most of which are trivial) as (x & y) x (x | ¬ y), and so on. Furthermore, if two columns have a row in which one entry is 0 and the other is 1, and another row in which the entries are 1 and 0, respectively, then no inequality relation exists between the corresponding logical expressions. So the question of whether or not f(x, y) g(x, y) is completely and easily solved for all binary logical functions f and g.

Use caution when manipulating these relations. For example, for ordinary arithmetic, if x + ya and zx, then z + ya, but this inference is not valid if “+” is replaced with or.

Inequalities involving mixed logical and arithmetic expressions are more interesting. Below is a small selection.

The proofs of these are quite simple, except possibly for the relation |xy| (xy). By |xy| we mean the absolute value of xy, which can be computed within the domain of unsigned numbers as max(x, y) − min(x, y). This relation can be proven by induction on the length of x and y (the proof is a little easier if you extend them on the left rather than on the right).