ALU, Shifters & Comparators

Ground-up guide to CMOS circuit design — transistors, gates, delay, power, memory, datapath and test

What an ALU Does

The ALU (Arithmetic Logic Unit) is the calculating heart of a processor. It takes two input numbers and a control code, and it produces one result plus some status flags. The control code picks the operation: add, subtract, AND, OR, XOR, compare, shift, and so on. The clever thing about an ALU is that many operations share the same hardware. Addition and subtraction use the same adder. The logic operations all run in parallel, and a multiplexer (a switch that picks one of several inputs based on a select code) chooses which result to send out. Sharing hardware saves area.

An ALU also outputs flags (single-bit status signals that describe the result). Common flags are zero, carry, negative, and overflow. Software reads these flags to make decisions, like jumping in a loop when a counter reaches zero.

Sharing Hardware for Add, Subtract, and Logic

Subtraction reuses the adder. To compute A minus B, the ALU adds A to the inverted B and sets the carry-in to 1. This works because of two's complement (the standard way to store signed numbers, where negating means invert all bits and add 1).

Compute A - B with A = 1010 (10), B = 0011 (3), 4-bit:
Invert B:        ~B = 1100
Add with carry-in 1:
1010 (A)
+ 1100 (~B)
+    1 (carry-in)
= 10111
Drop the 5th bit (carry-out): result = 0111 = 7
Check: 10 - 3 = 7   (correct)

So one control bit decides add vs subtract: it both inverts B and sets the carry-in. The logic operations (AND, OR, XOR, NOT) are computed bit by bit at the same time, in parallel with the adder. At the end, a multiplexer picks the chosen result.

Because everything runs in parallel and only the final multiplexer selects, the ALU delay is roughly the slowest single path, usually the adder, plus the multiplexer.

Barrel Shifters and Logarithmic Shifters

A shifter moves the bits of a number left or right by some amount. Shifting left by 1 doubles a number; shifting right by 1 halves it (for unsigned values). Shifting also lines up fields in data.

A slow shifter would move one bit position per cycle. That is too slow. A barrel shifter (a shifter that can move bits by any amount in a single pass) does the whole shift at once using layers of multiplexers. The smart way to build a barrel shifter is the logarithmic shifter (a shifter built from log-N stages, each shifting by a power of two). Stage 0 shifts by 0 or 1, stage 1 shifts by 0 or 2, stage 2 shifts by 0 or 4, and so on. By turning the right stages on, you build any shift amount from powers of two.

For wider words the stage count grows slowly. A 32-bit shifter needs only 5 stages, because log2(32) is 5. That is why logarithmic shifters are the standard fast design.

There are different shift types. A logical shift fills empty positions with 0. An arithmetic right shift fills with copies of the sign bit, so it keeps signed numbers correct. A rotate wraps bits around from one end to the other. The same barrel structure handles all of these with small changes to the fill logic.

Magnitude Comparators

A magnitude comparator tells you whether A is greater than, equal to, or less than B. It produces three outputs: A>B, A=B, A<B. Comparators are used everywhere, from sorting to address matching. The equal output is easy: A equals B only when every bit pair matches. You XOR each bit pair (XOR is 1 when bits differ) and check that all results are 0. The greater-than output works from the most significant bit (the leftmost, highest-value bit) downward: the first bit position where A and B differ decides the answer.

Compare A = 1011 (11) and B = 1001 (9), 4-bit unsigned:
Bit3: 1 vs 1 -> equal, keep looking
Bit2: 0 vs 0 -> equal, keep looking
Bit1: 1 vs 0 -> A's bit is 1, B's bit is 0  => A > B, stop
Result: A > B   (correct, 11 > 9)

A neat hardware trick: you can build a comparator from the subtractor you already have. Compute A minus B and look at the flags. If the result is zero, they are equal. The sign and carry flags together tell you which is larger.

Zero, Overflow, and Other Flags

Flags summarize the result in single bits so software can branch on them. Here are the most important ones. The zero flag is 1 when every bit of the result is 0. You build it by NOR-ing all the result bits together (NOR is 1 only when all inputs are 0). The carry flag is the carry-out of the most significant bit. For unsigned addition, a carry-out means the result was too big to fit, so it wrapped around. The overflow flag is for signed numbers. Overflow happens when the signed result does not fit in the available bits, so the sign comes out wrong. The clean rule: overflow occurs when the two inputs have the same sign but the result has a different sign.

Overflow example, 4-bit signed (range -8 to +7):
Add A = 0110 (+6) and B = 0101 (+5):
0110
+ 0101
= 1011  (this is -5 in signed 4-bit)
Both inputs positive, result negative => OVERFLOW = 1
True sum +11 does not fit in -8..+7, so the flag is correct.
Carry-out here = 0, so carry flag = 0.
Note: carry and overflow are different things.

The key confusion to avoid: carry is the unsigned "too big" signal, while overflow is the signed "sign wrong" signal. They are computed differently and can disagree, as the example above shows.

Interview Q&A

subtraction it inverts the second operand and sets the carry-in to 1, which is the same as adding the negative. A single control bit performs both the invert and the carry-in.

shifts by powers of two in log-N stages, so it can do any shift in one pass. A 32-bit shift needs only 5 stages instead of up to 31 sequential steps.

the empty top bits with 0. An arithmetic right shift fills them with copies of the sign bit, so it preserves the value of signed numbers when dividing by powers of two.

differ. If every XOR output is 0, all bit pairs match, so the numbers are equal. A NOR of all XOR outputs gives the equal flag.

carry-out of the top bit and signals unsigned overflow. The overflow flag signals signed overflow, set when both inputs share a sign but the result's sign differs. They are computed differently and can disagree.

result means equal; the borrow or sign flag tells which operand is larger. This reuses existing hardware instead of building a separate comparator.

Key Takeaways

• The ALU shares one adder for add and subtract via two's complement, with logic ops computed in parallel and a multiplexer selecting the result.
• A barrel shifter built as a logarithmic shifter does any shift in log-N stages of multiplexers.
• Logical, arithmetic, and rotate shifts differ only in how they fill the vacated bit positions.
• A magnitude comparator finds equality with XOR/NOR and greater-than from the most significant differing bit.
• The carry flag is the unsigned overflow signal; the overflow flag is the signed one, and the two are not the same.