How does less than and greater than work on a logical level in binary?

Question

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?

Solarize

Think about how you (not the computer) would do it for 2 numbers in decimal (i.e. "normal" numbers); I'm pretty sure the technique you describe is not how you would do it. – Fulgurate

compare the length and given the same length compare the most significant digit recursively? I guess this works in binary because the comparison is only either both 1, both 0, or different in which the 1 would signify the higher number. – Solarize

That's certainly better than what was in your question. – Fulgurate

Possible duplicate of assembly to compare two numbers – Butanol

@MartinSmith: I think OP would be more interested in how the compare instruction worked. – Fulgurate

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

 1101
  110
 +010
=====
  001

 1111
  101
 +010
=====
  000

 0001
  100
 +010
=====
  111

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

1111
 101
 011
====
 001

0011
 101
 001
==== 
 111

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.

Theo

I am working through it, thanks that is interesting. I am just seeing two's complement for the first time. The lowest I have actually coded is in C. So whether a variable is signed or not in a high level language, ultimately it is processed on ALU in two's complement (previously one's complement) and will have a sign bit (most significant bit)? – Solarize

I understand two's complement now and how to subtract and add using this method. I haven't accepted the answer because I am still trying to work out how the less-than and greater-than work. – Solarize

Answer 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

C = A - B

If C's sign bit is 1, then B > A. Otherwise, A >= B.

Interpol

O() depends on how you measure the size of the problem; if measured in the number of bits (which isn't unreasonable), it could be O(n). – Fulgurate

Still, what about unsigned or ambiguous values. I guess you have to know the endianess and specific types? – Solarize

"Ambiguous values"? – Fulgurate

ambiguous = if you don't know if the values will be signed or not – Solarize

This is actually wrong, consider A = minvalue, B = 1, then A - B wraps to a positive value however clearly B > A. – Kyat

@Solarize that doesn't make any sense, you interpret a value as signed or unsigned (or, frequently, it doesn't matter - but it does matter for greater-than), you can't get a value and then ask whether it's signed or unsigned, it's just a bunch of bits. – Kyat

@harold: this is actually how x86 implements the cmp instruction. See en.wikibooks.org/wiki/X86_Assembly/Control_Flow. The system will set flags after executing the instruction (presumably one of them has to do with overlfow?) although I don't know enough about x86 specifically to say. – Interpol

@DanielA.Thompson yea I know how it works, and it's not as simple as this (because well, it doesn't work). The signed comparisons also use the overflow flag. – Kyat

@harold I am confusing signed or unsigned in higher level languages I think. I am seeing now that ultimately the value will have a sign bit. So even an unsigned value in C, if it has arithmetic done to it, will be given a sign value? – Solarize