How does the computer determine whether a number is smaller or greater than another?

Question

It might sound like a stupid question but I'm really curious to know how a computer knows that $1<2$? Also, how does a computer know that the order of integer is $1,2,3,4,5,\ldots$ and alphabet is A,B,C,D,...? Is it somewhere stored in the hardware or does the operating system provide this kind of information?

Answer 1

First your integer numbers are converted into binary numbers. For example, the integer 2 is converted to 0010.

The CPU uses a digital comparator:

A digital comparator or magnitude comparator is a hardware electronic device that takes two numbers as input in binary form and determines whether one number is greater than or less than or equal to the other number.

Comparators are used in central processing units (CPU) and microcontrollers.

Source: https://en.wikipedia.org/wiki/Digital_comparator

In comparator hardware some gates are used (AND, OR, NAND, NOR, XOR, etc). These gates take binary inputs and give result in binary. The output can be seen from a truth table.

Inputs           Outputs
A   B     A>B    A=B    A<B
0   0     0       1      0
0   1     0       0      1
1   0     1       0      0
1   1     0       1      0

Here 0 & 1 are electronic voltages for the gate.
1 - Represents some threshold voltage which indicates some positive voltage.
0 - Represents the voltage below than the threshold.

E.g. suppose a comparator works on 5 volt (it is consideration for explanation) then:
Voltage more than 3 volt can be considered as binary-1.
Voltage below than 3 volt be considered as binary-0

If a gate gets one input as 3.5 volt and another input as 2 volt then it considers as, it takes one input as binary 1 & another input as binary 0.

These sequences of 1's & 0's are provided very fastly through the switching circuit.

The operation of a two bit digital comparator can be expressed as a truth table:

 Inputs                            Outputs
   A1   A0  B1  B0  A>B    A=B   A<B        
    0   0   0   0    0      1     0
    0   0   0   1    1      0     0
    0   0   1   0    1      0     0
    0   0   1   1    1      0     0
    0   1   0   0    0      0     1
    0   1   0   1    0      1     0
    0   1   1   0    1      0     0
    0   1   1   1    1      0     0
    1   0   0   0    0      0     1
    1   0   0   1    0      0     1
    1   0   1   0    0      1     0
    1   0   1   1    1      0     0
    1   1   0   0    0      0     1
    1   1   0   1    0      0     1
    1   1   1   0    0      0     1
    1   1   1   1    0      1     0

To quote from Wikipedia:

Examples: Consider two 4-bit binary numbers A and B such that


Here each subscript represents one of the digits in the numbers.

Equality

The binary numbers A and B will be equal if all the pairs of significant digits of both numbers are equal, i.e.,
. . .

Since the numbers are binary, the digits are either 0 or 1 and the boolean function for equality of any two digits and > can be expressed as

is 1 only if and are equal.

For the equality of A and B, all variables (for i=0,1,2,3) must be 1. So the quality condition of A and B can be implemented using the AND operation as

The binary variable (A=B) is 1 only if all pairs of digits of the two numbers are equal.

Inequality

In order to manually determine the greater of two binary numbers, we inspect the relative magnitudes of pairs of significant digits, starting from the most significant bit, gradually proceeding towards lower significant bits until an inequality is found. When an inequality is found, if the corresponding bit of A is 1 and that of B is 0 then we conclude that A>B. This sequential comparison can be expressed logically as:

Answer 2

It doesn't just "know", it checks every time. Basically, it does the same thing you would do: in order to compare, it checks (from the left) which number has the first digit that is larger than the corresponding one in the other number. Of course you have to add leading zeroes to the shorter number.

Letters are just numbers for the computer. Humans have assigned numbers, e.g. ASCII or Unicode, to letters so that number comparisons give the "correct" order for letters, too.

Answer 3

It's not the operating system that compares integers, the CPU is taking care of it. It's made on logical gates level, please refer to these slides to see how it can be done.

About the alphabet, in ASCII alphanumeric and other special characters are represented as integers so comparing them is also an integer comparison operation, which is performed by the CPU.

Answer 4

Actually, and in order to obtain the full image of it, I think it would be quite helpful to see with your own eyes the datapath of an actual CPU, for example MIPS:

As you may see, there is actually a second output from the ALU, which is a signal called Zero. It exists in order to perform fast branch operations, after determining whether the two operands of the comparison are equal to zero or not, as most comparisons within a program are about branches. Therefore, when you create a branch possibility in your code like:

if(a < b) {...}

This is translated into machine code, in mips for example: blt s0,s1,If $~\Rightarrow$ if a < b execute the instructions in the brackets, else continue with the execution outside the if{}. Specifically this instruction is a pseudo-instruction, which means that is translated into two other (simple) MIPS instructions $~\Rightarrow$
slt at,s0,s1 and then bne at,zero,If (slt: Set Less Than & bne: Branch on Not Equal).

Notice that signal zero is one of the inputs of the AND gate that determines where the Program Counter (PC) will take its value from: Assuming that Branch signal is '1', as we have a branch operation

• Zero = 0 $\Rightarrow$ The result of the subtraction was not equal to zero, so the Multiplexer will choose the address from Branch target and the execution will continue from the instruction that the branch leads.
• Zero = 1 $\Rightarrow$ The result was 0 (a = b) and so the MUX chooses the address from the adder where is calculated the address of the next instruction in normal execution (serial). No jump is executed as the condition (a < b) is invalid.

Hope I helped you see "under the bonnet". Feel free to ask for further analysis on this matter. Many things we take for granted, CPUs do them in a very fascinating way!

Answer 5

If you want to know about how an actual CPU does it, it's something like this.

A CPU operates on numbers of only up to a certain size. Nowadays that's usually 64-bit integers (we'll ignore floating-point numbers; the idea will be similar).

So we should recognize that

1. A CPU is storing numbers up to (say) 64 bits long in binary, in some format (probably 2s-complement but it doesn't matter too much what).

2. A CPU can't natively do anything with numbers bigger than that. We have to write software algorithms if we want to compare bigger numbers.

OK, so say we have two numbers that each fit in a normal-size 64-bit integer. Say $a$ and $b$. How does the processor compare them? Usually, it will subtract one from the other (that's a single native operation that is implemented in hardware).

Now the processor has stored a single number $a-b$. Again, this number is at most 64 bits, so it fits in a "register" that's 64 bits long, which is where we store our numbers for calculation. Now it just checks if $a-b$ is less than zero. It does this with a single native operation that could work, on the circuit level, like the comparison algorithms that the other answers have described. It will look a lot like those, but all implemented in circuits (because the number is at max 64 bits, this is a certain-size circuit that we can hardwire and stick on the CPU.) Depending on how the CPU stores numbers, it might be even faster because it might be that all negative numbers have the first bit set to one, or something like that. Either way, there's only 64 bits total, so we can definitely check if this number is negative.

If it is, then we know $a < b$; if not, then we know $a \geq b$.

Now, for bigger numbers, we have to implement something in software that will use these small comparisons as subroutines.

Answer 6

To answer this question let me first point out that there are at least two levels on abstraction for the comparison numbers on a computer, the machine-level, and the software level.

Comparing numbers on the machine level

In today's computer the CPU has a rich set of instruction. These instructions include for example loading a memory cell into a register, incrementing a register, adding two registers, and many many more. There have also to be instructions for conditional jumps. For example the processors in Intel's x86 family support the instructions jnz (jump if not zero), jne (jump not equal), and so on. If those would be missing then the CPU would not be Turing-complete. The variables from which the conditional jump depends are stored in the registers. Thus, these instructions are hard-wired in the architecture of the CPU as a circuit build from logical gates. This is the only way how the CPU can compare two numbers.

Comparing numbers on the software level

If you compare two numbers, say in a c++ program, then this is translated into machine code and therefore carried out on the machine level. However, such an comparison can be more complex. It really depends on the data type you used how the comparison is translated into machine code. Just one example, the numbers you want to compare are from the 64 Bit words but your machine has only works with 32 bits. Then this number does not fit in a register, hence the compiler will break down the comparison into a sequence of comparisons on the machine code level. The same applies for more complicated data types/data structures, representing for example rational numbers, or strings, or characters. Hence when you have to compare two characters, this is to translated by software (operating system, compiler, interpreter,...) into machine code. The actual translation depends on the encoding of the character/number.

As a final remark I want to point out that standard CPUs can also work with different representations of numbers (signed integers in 1- or 2-complement representation, floats). Also comparisons might be carried out in other parts of the computer such as the GPU.

Answer 7

other answers are good, just throwing another one out there for further consideration/insight with a CS flavor/twist. one can construct an FSM, a finite state machine, that can compare two binary numbers of any length, starting pairwise from the most significant bits and working to least significant bit (LSB). it can also be used to conceptualize the digital comparator given in another answer, yet the FSM does not require finite length binary numbers. it can even work on integers with binary fractions after the LSB. it has an inductive and recursive flavor and can be proven correct by simple induction. it runs as follows:

• input the top two binary digits as a pair (a,b)
• if a=1 and b=0 the left number is larger.
• if a=0 and b=1, the right number is larger.
• otherwise the numbers are "equal up til now", advance to next pair.

in other words the largest number is the one with the first occurrence of a bit that is one and the other is zero, after an initial run of zero or more identical 1's. a finite-length digital comparator made of gates or 1-bit comparators can be seen as based on fixing the length of this FSM operation to some fixed number of bits. (yes there is a strong correspondence between all finite circuits and "fixing the length" of FSM computations.)

this may seem like a theoretical exercise but actually, the logic in software to represent arbitrary precision numbers operates something analogous to this FSM, except encoded in a computer loop that can be seen as looping over or simulating the steps of the FSM (an efficient implementation might track via an index the location of the MSB).

---

also, lets reasonably interpret/generalize this question as not limited to integers. the question refers to integers but the title only refers to numbers. surprisingly nobody else mentioned floating point arithmetic so far.

basically that works by comparing the exponent and the mantissa where a number is in the form $a \times 10^b$, $a$ the mantissa, b the exponent. the mantissa can be normalized to a number where the first digit is always nonzero. then to compare two numbers the logic first compares the exponents $b$, and if they are unequal, it can return a result without comparing the mantissas (using say the comparator circuit). if the exponents are equal, it compares the mantissas.