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?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ 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. $\endgroup$– Andrej BauerCommented Dec 9, 2012 at 17:21
-
$\begingroup$ @AndrejBauer: Actually, he hasn't logged on since asking the question. Maybe he now knows all he needs to. $\endgroup$– Dave ClarkeCommented Dec 13, 2012 at 9:28
-
$\begingroup$ @AndrejBauer Hehe I hope so! To be encouraging to those who answered, I want to point out that whether Ricky Stam ever saw this answer or not isn't too important! The goal of Stack Exchange is to create a repository for humanity containing quality questions and quality answers! Even more purely, it's a place where we can ponder quality questions and provide answers. That we've participated is enough! That others have seen the discussion is even better. (: $\endgroup$– JDGCommented Aug 26, 2020 at 21:11
Add a comment
|
7 Answers
$\begingroup$
$\endgroup$
4
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.
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:
-
3$\begingroup$ Whoa, what's going on here? $\endgroup$ Commented Oct 18, 2013 at 14:55
-
1$\begingroup$ "First your integer numbers are converted into binary numbers"... wrong, there is only binary numbers in the memory at the first place, its all 1's and 0's in the machine level, so there is not a "convertion" , 2 is represented as 10 from start to end.. $\endgroup$ Commented Mar 23, 2017 at 7:06
-
-
$\begingroup$ The two bit digital comparator table is incorrect. ijesi.org/papers/Vol(2)1%20(version%202)/C211324.pdf when A1, A0 are both zero but B0 and B1 are 0, 1 A>B will be 0, for example. $\endgroup$ Commented May 22, 2017 at 18:15
$\begingroup$
$\endgroup$
3
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.
-
$\begingroup$ Also, this is usually termed "lexicographic order". We can usually think of it as first ordering by length (shortest to longest), then alphabetically. $\endgroup$– usulCommented Dec 4, 2012 at 22:39
-
$\begingroup$ @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. $\endgroup$– RaphaelCommented Dec 4, 2012 at 23:15
-
$\begingroup$ 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.... $\endgroup$– usulCommented Dec 4, 2012 at 23:39
$\begingroup$
$\endgroup$
0
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.
answered Dec 1, 2012 at 9:28
$\begingroup$
$\endgroup$
1
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!
-
$\begingroup$ Ethan, how does "less" operation work on this datapath? As I understand, you described operation "not equal". What does "slt" instruction? $\endgroup$– osgxCommented Dec 9, 2012 at 1:58
$\begingroup$
$\endgroup$
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
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).
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.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
