implement eq, lt gt in assembly without jumps

Question

Is it possible to write logic using only the AND, OR, and NOT operators to compare 2 operands and return true/false (-1, 0) without the use of jumps? If so, can you please give me some hints as it looks impossible to me. I am trying to implement eq, lt and gt in the assembly language of the book "The Elements of Computing Systems".

Answer 1

Getting a result of either -1 or 0 (or of either 1 or 0, for that matter) from your comparison operations is impossible if you are using only bitwise logical operators, and add/subtract where the carry is lost:

• For the bitwise operators, bit n of the result depends only on bit n of the two operands.

• For addition, consider how a binary addition works: bit n of the result may be influenced by bit n, and bits to the right of bit n (via carries), of each of the operands; but cannot be influenced by any bits to the left of bit n in the operands. (You could consider this to be a generalisation of the observation that adding two even numbers cannot give an odd result.)

• As a single addition or bitwise op cannot propagate any information from the left of bit n of the operands into bit n of the result, neither can any composition of additions or bitwise ops; and a subtraction (assuming 2's complement here) can be considered as just such a composition: x-y = x+(NOT y)+1.

So you can't get a result of 0 for 2==2, but -1 (or 1) for 2==4, for example: bit 0 of the desired result is different in each case, but the result can depend only on bit 0 of the two operands, which are the same in each case.

If your true and false values differ only in the top (i.e. leftmost) bit, it can be done.

For example, with 8 bit values: use 0x80 for true and 0 for false; then x == y could be implemented as (NOT((x - y) OR (y - x))) AND 0x80.

The problem as originally stated can be solved if the available operations are extended to include a right shift, or if the ADD operation can produce a carry which may be added back in to the bottom of the result.

Answer 2

XOR a, b

will result in 0 if a and b are equal, and something nonzero otherwise.

SUB a, b
AND a, SIGN_BIT

(where SIGN_BIT is a mask to remove everything except ... the sign bit)

will result in zero if a is greater than b, and nonzero if a is less than or equal to b (assuming 2's completent).

Answer 3

A Equal B can be expressed in terms of xor:

(A AND (NOT B)) OR ( A AND (NOT B))

This will output 0 if A==B and something != 0 if it's not

For A less than B you can use (A - B AND SIGN_MASK)

,where SIGN_MASK masks away everything except the sign bit, would give you a true value of MAX_NEGATIVE_INTEGER and a false value of 0.

Greater than can be trivially constructed from less than

Answer 4

Just in case this is a pure theoretical question: since you're operating on a finite set of operands, all possible functions can be expressed using only OR, AND and NOT.

See Disjunctive normal form for further explanation.

For practical purposes, Anons answer is more useful :-) ...

EDIT: Even my theoretical answer might not be true: Application of disjunctive normal form to this problem would require shift operations, since each single bit of the output word depends on all bits of the input bits. I have not yet figured out how to implement shifts using AND, OR, NOT and arithmetic (and I'm not sure whether that's possible at all ...)

I leave the post though as negative example of premature answering ...