18

E.g. when comparing two integers as follows in a C-like language:

if (3 > 2) {
    // do something
}

How is the judgement whether 3 is greater than 2 (true) or not (false) made internally?

  • 19
    The current answer are ok for the case when the comparation is about variable expression, but lack a disclaimer that many modern compilers will look at your piece of code, detect that the expression will always be true (because of literals) and just ignore the if altogether, going straight to coding do something. – SJuan76 Aug 5 '17 at 10:49
  • 3
    Possible duplicate of How Do Computers Work? – user22815 Aug 5 '17 at 18:41
  • 3
    @Snowman I disagree. Any "how does this work" programming inquiry can be condensed down to that question, but that does not make them duplicates. – user1643723 Aug 5 '17 at 19:34
  • 1
    @user1643723 It does when the function in question is a specific opcode. – chrylis Aug 5 '17 at 19:52
  • 1
    @user1643723 The question is asking about how a computer performs a basic operation, and the top answer discusses logic gates and logic tables. Two topics which are covered extensively in the dupe target's top answer, which also answers your question. – user22815 Aug 6 '17 at 21:57
60

All the way down the rabbit hole, eh? OK I'll give it a try.

Step 1. From C to machine language

The C compiler transforms your comparison to opcodes stored in machine language. Machine language is a series of numbers that the CPU interprets as instructions. In this case there would be two opcodes: "subtract with carry" and "jump if carry." In other words, 2 is subtracted from 3 in one instruction, and the next instruction checks to see if it overflowed. These would be preceded by two instructions to load the numbers 2 and 3 into locations where they can be compared.

MOV AX, 3    ; Store 3 in register AX
MOV BX, 2    ; Store 2 in register BX
SUB AX, BX   ; Subtract BX from AX
JC  Label    ; If the previous operation overflowed, continue processing at memory location "Label"

Each of the above has a binary representation; for example, the code for SUB is 2D hex, or 00101101 in binary.

Step 2. Opcodes to ALU

Arithmetic opcodes like ADD, SUB, MUL, and DIV perform basic integer math using an ALU or Arithmetic Logic Unit built into the CPU. Numbers are stored in registers by some opcodes; other opcodes instruct the chip to call the ALU to do math on whatever is stored in registers at the time.

Note: At this point we are well beyond anything that any software engineer would worry about if working with a 3GL like C.

Step 3. The ALU, half-adder, and full-adder

Did you know that all mathematical operations you know of can be reduced to a series of NOR operations? And that is exactly how the ALU works.

The ALU only knows how to work with binary numbers, and can only perform logical operations like OR, NOT, AND, and XOR. Implementation of binary addition and subtraction are accomplished with a series of logical operations arranged a certain way, in a subsystem known as an adder. These subsystems are composed of a network of "half-adders" that operate on two bits and determine their single-bit sum and a single-bit carry flag. By chaining these together, the ALU can perform operations on numbers with 8, 16, 32 etc. bits.

Half-Adder

What about subtraction? Subtraction is just another form of addition:

A - B = A + (-B)

The ALU computes -B by taking the two's complement of B. Once it is converted to negative, submitting the value to the adder will result in a subtraction operation.

Step 4: The final step: On-chip transistors

The adders' operations are implemented using a combination of electrical components that interact to create "logic gates," such as those found in transitor-transistor logic or TTL, or in CMOS. Click here for a few examples to see how these are wired up.

On a chip, of course, these "circuits" are implemented in millions of tiny bits of conductive and nonconductive material, but the principle is the same as if they were full-sized components on a breadboard. Watch this video which shows you all the transistors on a microchip through the lens of an electronic microscope.

Some additional notes:

  1. The code you wrote would actually be precomputed by the compiler and not executed at run time, because it is composed solely of constants.

  2. Some compilers don't compile to machine code but introduce yet another layer, such as Java bytecode or .NET intermediate language. But in the end it all gets executed via machine language.

  3. Some mathematical operations aren't actually computed; they are looked up in massive tables on an arithmetic coprocessing unit, or contain a combination of lookup and computation or interpolation. An example would be the function to compute a square root. Modern PC CPUs each have a floating point coprocessing unit built into each CPU core.

  • 3
    FWIW, referencing to TTL may be confusing as virtually no modern processors use TTL signalling, most using CMOS FETs and lower voltages instead of 5v BJTs. – whatsisname Aug 5 '17 at 5:06
  • 2
    CMOS would definitely be a better reference than TTL, as @whatsisname suggests, because not only is it more accurate to what goes on in modern processors, it's also conceptually much simpler. – Jules Aug 5 '17 at 11:41
  • 3
    @JackAidley that's what this part means: "In other words, 2 is subtracted from 3 in one instruction, and the next instruction checks to see if it overflowed." – KutuluMike Aug 5 '17 at 14:43
  • 1
    Nitpicking: I suppose CMP would be used, not SUB - but then again that is more or less a "SUB wher the result is ignored and only the flags are set" – Hagen von Eitzen Aug 5 '17 at 16:25
  • 5
    Your definitions of half- and full-adder are incorrect. A half adder takes two 1-bit inputs and returns the sum and carry. A full adder takes an additional carry-in input but is still only single bit. There are many ways to create a N-bit adder, the simplest being a ripple-carry adder which is just a chain of N full adders. In practice for larger Ns this has a pretty bad delay so more complex designs are used in modern CPU designs. – Voo Aug 5 '17 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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