How does less than and greater than work on a logi

I see how equality could work by just comparing bit patterns, but how would one write one's own less than and greater than operators? What is the actual process to mechanically compare values to each other?

回答1:

I assume you want to just know how logic does it? And mimic that? Well here goes:

First off you have to talk about unsigned greater than or less than vs signed greater than vs less than because they matter. Just do three bit numbers to make life easier, it all scales up to N bits wide.

As processor documentation usually states a compare instruction will do a subtraction of the two operands in order to generate flags, so it is a subtract that doesnt save the answer just modifies the flags. That then later jump or branch on some flag pattern can be used. Some processors dont use flags but have a similar solution, they still use the equivalent of flags but just dont save them anywhere. compare and branch if greater than kind of an instruction instead of separate compare and branch if greater than instructions.

What is a subtract in logic? Well in grade school we learned that

a - b = a + (-b).

We also know from intro programming classes that a negative in twos complement means invert and add one so

a - b = a + (~b) + 1.

Note ones complement means to invert ~b in C means invert all the bits it is also known as taking the ones complement.

so 7 - 5 is

   1
 111
+010
=====

Pretty cool we can use the carry in as the "plus one".

1111
 111
+010
=====
 010

So the answer is 2 with the carry out set. Carry out set is a good thing means we didnt borrow. Not all processors do the same but so far with a subtract we use an adder but invert the second operand and invert the carry in. If we invert the carry out we can call it a borrow, 7 - 5 doesnt borrow. Again some processor architectures dont invert and call it a borrow they just call it carry out. It still goes into the carry flag if they have flags.

Why does any of this matter? Just hang on.

Lets look at 6-5 5-5 and 4-5 and see what the flags tell us.

So what this means is the carry out tells us (unsigned) less than if 0. If if 1 then greater than or equal. That was using a - b where b is what we were comparing against. So if we then do b - a that would imply that we can get (unsigned) greater than with the carry bit. 5 - 4, 5 - 5, 5 - 6. We already know what 5 - 5 looks like zero with the carry out set

Yep we can determine (unsigned) greater than or equal or (unsigned) less than or equal using the carry flag. Not less than is the same as greater than or equal and vice versa. You just need to get the operand you want to compare against in the right place. I probably did this backward from every compare instruction as I think they subtract a - b where a is what is being compared against.

Now that you have seen this you can easily scratch out the above math on a piece of paper in a few seconds to know which order you need things and what flags to use. Or do a simple experiment like this with a processor you are using and look at the flags to figure out which is subtracted from which and/or whether or not they invert the carry out and call it a borrow.

We can see from doing it with paper and pencil as in grade school that addition boils down to one column at a time, you have a carry in plus two operands, and you get a result and a carry out. You can cascade the carry out to the carry in of the next column and repeat this for any number of bits you can afford to store.

Some/many instruction sets use flags (carry, zero, signed overflow, and negative are the set you need to do most comparisons). You can see I hope that you dont need assembly language nor an instruction set with flags, you can do this yourself with a programming language that has the basic boolean and math operations.

Untested code I just banged out in this edit window.

unsigned char a;
unsigned char b;
unsigned char aa;
unsigned char bb;
unsigned char c;

aa = a&0xF;
bb = (~b)&0xF;
c = aa + bb + 1;
c >>=4;
a >>=4;
b >>=4;
aa = a&0xF;
bb = (~b)&0xF;
c = c + aa + bb;
c >>=4;

And there you go, using an equals comparison, compare c with zero. And depending on your operand order it tells you (unsigned) less than or greater than. If you want to do more than 8 bits then keep on cascading that add with carry indefinitely.

Signed numbers...

ADDITION (and subtraction) LOGIC DOES NOT KNOW THE DIFFERENCE BETWEEN SIGNED AND UNSIGNED OPERANDS. Important to know. This is the beauty of twos complement. Try it yourself write a program that adds bit patterns together and prints out the bit patterns. Interpret those bit patterns input and output as all unsigned or all signed and you see this works (note some combinations overflow and the result is clipped).

Now saying that the flags do vary for subtraction comparisons. We know from grade school math where we carry the one or whatever over as we see in binary as well. The carry out is an unsigned overflow for unsigned. If set you overflowed we have a 1 we cant fit into our register so the result is too big we fail. Signed overflow though is the V bit which tells us if the carry IN and carry OUT of the msbit were the same or not.

Now lets use four bits, cause I want to. We can do the 5 - 4, 5 - 5, and 5 - 6. These are positive numbers so we have seen this but we didnt look at the V flag nor N flag (nor z flag). The N flag is the msbit of the result which indicates negative using twos complement notation, not to be confused with a sign bit although it is as a side effect, it is just not a separate sign bit that you remove from the number.

11111
 0101  
 1011  
=====
 0001
c = 1, v = 0, n = 0
11111
 0101
 1010
=====
 0000
c = 1, v = 0, n = 0
00011
 0101
 1001
=====
 1111
c = 0, v = 0, n = 1

Now negative numbers -5 - -6, -5 - -5, -5 - -4

10111
 1011
 1010
=====
 0110
c = 0, v = 1, n = 1

You know what, there is an easier way.

#include <stdio.h>
int main ( void )
{
    unsigned int ra;
    unsigned int rb;
    unsigned int rc;
    unsigned int rd;
    unsigned int re;
    int a;
    int b;

    for(a=-5;a<=5;a++)
    {
        for(b=-5;b<=5;b++)
        {
            ra = a&0xF;
            rb = (-b)&0xF;
            rc = ra+rb;
            re = rc&8;
            re >>=3;
            rc >>=4;
            ra = a&0x7;
            rb = (-b)&0x7;
            rd = ra+rb;
            rd >>=3;
            rd += rc;
            rd &=1;
            printf("%+d vs %+d: c = %u, n = %u, v = %u\n",a,b,rc,re,rd);
        }
    }
    return(0);
}

and a subset of the results

-5 vs -5: c = 1, n = 0, v = 0 
-5 vs -4: c = 0, n = 1, v = 0 

-4 vs -5: c = 1, n = 0, v = 0 
-4 vs -4: c = 1, n = 0, v = 0 
-4 vs -3: c = 0, n = 1, v = 0 

-3 vs -4: c = 1, n = 0, v = 0 
-3 vs -3: c = 1, n = 0, v = 0 
-3 vs -2: c = 0, n = 1, v = 0 

-2 vs -3: c = 1, n = 0, v = 0 
-2 vs -2: c = 1, n = 0, v = 0 
-2 vs -1: c = 0, n = 1, v = 0 

-1 vs -2: c = 1, n = 0, v = 0 
-1 vs -1: c = 1, n = 0, v = 0 
-1 vs +0: c = 0, n = 1, v = 0 

+0 vs -1: c = 0, n = 0, v = 0 
+0 vs +0: c = 0, n = 0, v = 0 
+0 vs +1: c = 0, n = 1, v = 0 

+1 vs +0: c = 0, n = 0, v = 0 
+1 vs +1: c = 1, n = 0, v = 0 
+1 vs +2: c = 0, n = 1, v = 0 

+3 vs +2: c = 1, n = 0, v = 0 
+3 vs +3: c = 1, n = 0, v = 0 
+3 vs +4: c = 0, n = 1, v = 0

And I will just tell you the answer...You are looking for n == v or not n == v. So if you compute n and v, then x = (n+v)&1. Then if that is a zero they were equal, if that is a 1 they were not. You can use an equals comparison. When they were not equal b was greater than a. Reverse your operands and you can check b less than a.

You can change the code above to only print out if n and v are equal. So if you are using a processor with only an equals comparison, you can still survive with real programming languages and comparisons.

Some processor manuals may chart this out for you. They may say n==v for one thing or not z and n!=v for the other (LT vs GT). But it could be simplified, from grade school the alligator eats the bigger one a > b when you flip it b < a. So feed the operators in one way and you get a > b, feed them the other way you get b < a.

Equals is just a straight bit comparison that goes through a separate logic path, not something that falls out of the addition. N is grabbed from the msbit of the result. C and V fall out of the addition.

回答2:

One method that is O(1) over all numbers in the given domain (keeping the number of bits constant) would be to subtract the numbers and check the sign bit. I.e., suppose you have A and B, then