How does an Arithmetic Logic Unit do comparisons?

Question

I am taking a course of system tools and architecture in my University and the first class is about how CPU and RAM talks and how CPU process the data. As explained by the Prof, CPU has an ALU (Arithmetic Logic unit) which performs arithmetic such as additions and comparisons. But he did not explain how it does it.

I did some searching and found this link which directs to a youtube video that explains how addition is performed - well explained for beginners. Even this link explains that CPU directs arithmetic processing to ALU but does not deal with how ALU performs it.

My question is about how an ALU does comparison. As humans, we know 5 is less than 7.

But how does an ALU know this; is it hard-coded in some way? I am sure it must use some logic for comparisons: what is that logic?

Mannose

Most ALUs probably subtract and then inspects the sign bit of the result. – Wilhelm

Yep, perform the operation but don't store it in a user visible register – Circinus

@TedHopp: That wouldn't work unless the output is wider than the inputs, to make signed overflow impossible. e.g. in 8-bit, -128 < 1, but -128 - 1 wraps to 127. That's why, after FLAGS are set by sub or cmp, jl is taken if SF != OF on x86 for example. (felixcloutier.com/x86/jcc). So sign of result, unless signed-overflow happened, then the opposite. – Enswathe

Answer 1

Are you familiar with how typical ALUs set flags to indicate that overflow occurred, or that the result of an operation is zero or negative? Typically, a comparison is performed by doing a subtraction and updating the flags but discarding the numerical result.

For example, if you subtract 7 from 5, the result is negative. Therefore, 5 is less than 7.

---

I should note that this is definitely not the only way in which it is possible to implement comparison. With a little thought, one can construct an algorithm (which could be made into a circuit) to directly compare the binary representations of two integers without subtracting them. However, subtraction is such a fundamental operation that (almost) all CPUs implement it quite efficiently already, and there is no reason not to reuse that implementation for comparisons.

Compact

I just know that ALU sets flags for comparisons. (in fact it seems it uses 4 flags - greater,smaller,equal but I cannot guess the fourth flag). but yes, I do not know how ALU set flags to indicate overflow. – Mannose

Usually, there are no “greater” or “smaller” flags; instead there is some variant of negative, zero, overflow, carry (unsigned overflow), and sometimes more besides. These flags provide enough information to determine how the two operands compare. – Compact

so the primary two operations are addition and subtraction, everything else uses these two operations under the hood correct? – Mannose

A modern CPU implements lots of other fundamental operations. You almost always at least have some bitwise operations like AND, OR, NOT, XOR. Multiplication is commonly implemented as a single operation, division is less common but definitely present on “big” processors, and many more exotic operations often exist as well. You’ll learn all of this later in your course, don’t worry. – Compact

I did not know one can construct an algorithm into a circuit! may be I should give a try with quicksort algoirthm in a circuit, but that might take entire motherboard space!!! – Mannose

Answer 2

Chain of relays or transmission gates (74CBT3253). Pick your comparison test < = >, or use to find borrows without ripple.

Manchester Magnitude comparator:

Acrimonious

Can you include a brief elaboration, for those unfamiliar with these processes? – Indented