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".

Hermes

is it really necessary to use only and, or and not? because you will generally need something like sub (which is technacilly expressble through the mentioned operators, but it would be a bit of a pain in the ass to manually transverse the carry. if you allow sub and shift operators it becomes relatively easy though – Misdeem

Do you need to deal with negative numbers too? – Paralyze

sorry, yes, yes you can add and subtract and assign values to registers, the assembly ALU computations are 0, 1 -1, x, y, not x, not y, -x, -y, x+1, y+1, x-1, y-1, x+y, x-y, y-x, x AND y, x OR y – Hermes

Which assembly language are you using? – Effective

Which assembly language are you using? It is from this book : www1.idc.ac.il/tecs – Hermes

I suppose, you have no status flags register? – Campy

there are zero and negative flags outputing from the alu but they go to the program counter for use in the jump decision and aren't outputed outside the cpu – Hermes

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.

Demurrer

Thanks, I think this is a great answer, very clear and understandable. – Hermes

You can do it with shifts, which is also bitwise. Unfortunately it's not allowed in the question – Towboat

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).

Galileo

Thanks. the problem I had was that the output has to be -1 or 0, I was able to output -1 where the tests were true but if the result was false the output would as you said be 'something'. I wanted to be able to force this something to 0, if it wasn't a -1 – Hermes

Note that your comparison doesn't do the right thing if the subtract overflows =/ – Headsman

An arithmetic right-shift of the maximum amount will result in -1 if the input is negative, and 0 otherwise – Galileo

Answer 3

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 ...

Campy

Answer 4

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

Misdeem

Thanks, how can I convert the !=0 to a definite value (say 1) for all cases where the !=0 is not 0. That is the stumbling block for me – Hermes

Answer 5

we're going through the same book and just hit this problem.

The best solution we could find was to generate unique labels, and then use the JEQ command to jump to the expected one, then jump to a label further down when we were done.

Pseudocode:

if they're equal, jump to EQUAL

// not equal section
push constant false
jump to DONE

// equal section
(EQUAL)
push constant true

// done section
(DONE)

Here is how we specifically implemented this (in Ruby).

Rosabella

Answer 6

x86 CPUs from some point in history onward have had "conditional move" ops.

Anabaptist

Answer 7

all the arithmetic operations in the assembly language that you are talking about come with a possibility of conditional jumps based on the result of the operation (=0? and >0?), which can be used to get the desired boolean result.

Incontrollable