Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
1  
In order that this question may be answered satisfactory, we would have to know how much Ricky Stam knows about computer architecture. From the question it looks like very little, so none of the fancy answers below will be comprehensible to him. –  Andrej Bauer Dec 9 '12 at 17:21
    
@AndrejBauer: Actually, he hasn't logged on since asking the question. Maybe he now knows all he needs to. –  Dave Clarke Dec 13 '12 at 9:28

7 Answers 7

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

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. Examples of digital comparator include the CMOS 4063 and 4585 and the TTL 7485 and 74682-'89.

The analog equivalent of digital comparator is the voltage comparator. Many microcontrollers have analog comparators on some of their inputs that can be read or trigger an interrupt.

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

Examples: Consider two 4-bit binary numbers A and B such that
enter image description here
enter image description here
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.,
enter image description here . enter image description here . enter image description here. enter image description here

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

enter image description here is 1 only if enter image description here and enter image description here are equal.

For the equality of A and B, all enter image description here 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
enter image description here
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:

enter image description here

share|improve this answer
1  
Whoa, what's going on here? –  Gilles Oct 18 '13 at 14:55

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.

share|improve this answer
    
Also, this is usually termed "lexicographic order". We can usually think of it as first ordering by length (shortest to longest), then alphabetically. –  usul Dec 4 '12 at 22:39
    
@usul That reminds me that the particulars of comparing integers obviously depends on the particular encoding; what I describe works for "naive" binary numbers which may be far from what an actual CPU uses. –  Raphael Dec 4 '12 at 23:15
    
Yep, absolutely. I've been thinking about Turing Machines too much recently :). Real machines don't quite fit what we've said here all the time.... –  usul Dec 4 '12 at 23:39

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.

share|improve this answer
    
Thank you very much for your help! –  Ricky Stam Dec 1 '12 at 9:32

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: enter image description here

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!

share|improve this answer
    
Ethan, how does "less" operation work on this datapath? As I understand, you described operation "not equal". What does "slt" instruction? –  osgx Dec 9 '12 at 1:58

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.