The ALU Flags
This is the last article of the ALU section, and it is about four bits. Every if in every program ends up as a test on them. When a processor evaluates if (a > b) it does not run a greater-than circuit; it subtracts $b$ from $a$, looks at four bits that come out of the adder, and decides. We generated those bits in the last article without much comment. Now they get proper attention: how each is built, what it means exactly, and how they combine into the signed and unsigned comparisons that ARM and x86 define.
Why flags exist
The ALU has two outputs. One is the result. The other is a set of one-bit answers to questions about the result: was it zero, was it negative, did unsigned arithmetic wrap, did signed arithmetic overflow. A branch instruction does not need the result; it needs those answers. Keeping them as separate bits, and storing them in a status register (CPSR on ARM, EFLAGS on x86), gives the processor a short path from an arithmetic operation to a branch decision. That path is among the most timing-critical in a processor, because it sets how quickly a branch resolves.
Zero
$$Z = \overline{R_{N-1} + \cdots + R_1 + R_0}$$
A NOR across every result bit. For 4 bits that is a two-level NOR tree. For 32 bits it is five levels, and in a fast processor the zero detect is computed speculatively from partial adder results so that it does not add five gate delays after the sum settles.
Z is the most used flag. Equality tests (==, !=) and loop counters both come down to it. CMP A, B computes $A - B$, and Z = 1 means $A = B$.
Negative
$$N = R_{N-1}$$
The sign bit of the result, a wire. It means “negative” only if you are treating the result as two’s complement. For unsigned values the top bit is just the largest magnitude bit; $1010$ has N = 1 and is the unsigned number 10. Reading N as “negative” in an unsigned context is a common conceptual error.
Carry
$$C = C_{out}$$
The carry out of the top full adder. After an addition, C = 1 means the unsigned sum exceeded $2^N - 1$ and wrapped. For 4 bits, $12 + 5 = 17$ gives result $0001$ and C = 1.
After a subtraction done as $A + \bar{B} + 1$, the carry out has the opposite sense: C = 1 means no borrow, $A \geq B$ unsigned; C = 0 means a borrow, $A < B$. Instruction sets differ on how they present this. ARM keeps C = 1 for “no borrow”. x86 inverts it, so CF = 1 means a borrow occurred. Check the architecture manual before writing comparison logic.
The carry flag is also the input to add-with-carry, which is how arithmetic wider than the ALU is done.
Overflow
$$V = c_{N-2} \oplus C_{out}$$
The XOR of the carry into the top bit and the carry out of it. Signed overflow can happen in only two ways: two positives add to a negative pattern, or two negatives add to a positive one. In both cases the carry into the sign bit and the carry out of it disagree, and the XOR catches exactly that. One gate.
When each flag is valid
| Operation | Z | N | C | V |
|---|---|---|---|---|
| ADD | valid | valid | unsigned overflow | signed overflow |
| SUB | valid | valid | no-borrow when 1 | signed overflow |
| AND, OR, XOR, NOT | valid | valid | undefined | undefined |
| PASSA, PASSB | valid | valid | undefined | undefined |
“Undefined” in a real instruction set usually means the flag keeps its previous value or is cleared. ARM specifies per instruction which flags the S-suffixed form updates.
ARM and x86
On ARM, the top four bits of the CPSR are N, Z, C and V (bits 31 to 28). Flags are updated only by instructions with the S suffix, such as ADDS and SUBS, so ordinary arithmetic leaves them alone.
On x86, EFLAGS has CF (bit 0), ZF (bit 6), SF (bit 7, the same as N) and OF (bit 11, the same as V). Most arithmetic and logic instructions update the flags automatically. CMP is SUB with the result discarded, and TEST is AND with the result discarded.
Deriving the comparisons
This is the part worth working through by hand. A comparison is CMP A, B, which computes $A - B$ and sets the flags.
Unsigned A > B
$A > B$ unsigned means $A - B$ did not borrow and is not zero. In ARM’s convention that is C = 1 (no borrow) and Z = 0. ARM calls this condition HI.
$A \geq B$ unsigned is just C = 1 (CS or HS). $A < B$ unsigned is C = 0 (CC or LO).
Signed A > B
Signed comparison has to allow for overflow, which can flip the sign of the result.
If there was no overflow (V = 0), the result’s sign is right: $A > B$ when N = 0 and Z = 0.
If there was overflow (V = 1), the result’s sign is wrong. A result that looks negative (N = 1) was really positive, so $A > B$; a result that looks positive was really negative. So with V = 1, $A > B$ when N = 1 and Z = 0.
Put the two cases together: in both, N equals V, and Z is 0.
$$A > B \text{ signed} \iff Z = 0 \text{ and } N = V$$
That is ARM’s GT condition. Drop the Z requirement and you have GE, $A \geq B$; negate it and you have LT, $N \neq V$.
The ARM condition codes
| Condition | Mnemonic | Test | Use |
|---|---|---|---|
| equal | EQ | Z = 1 | == |
| not equal | NE | Z = 0 | != |
| carry set | CS, HS | C = 1 | unsigned ≥ |
| carry clear | CC, LO | C = 0 | unsigned < |
| negative | MI | N = 1 | result < 0 |
| non-negative | PL | N = 0 | result ≥ 0 |
| overflow | VS | V = 1 | |
| no overflow | VC | V = 0 | |
| unsigned higher | HI | C = 1 and Z = 0 | unsigned > |
| unsigned lower or same | LS | C = 0 or Z = 1 | unsigned ≤ |
| signed ≥ | GE | N = V | |
| signed < | LT | N ≠ V | |
| signed > | GT | Z = 0 and N = V | |
| signed ≤ | LE | Z = 1 or N ≠ V | |
| always | AL | unconditional |
Every row follows from the flag definitions by the same reasoning as the GT case. When you write if (a > b) in C for ARM, the compiler emits a CMP followed by a BLE, branch if less or equal, around the body; the branch unit evaluates “Z = 1 or N ≠ V” on the status register bits, which is about three gates.
The hardware, in one table
| Flag | Expression | Hardware | Delay after the result |
|---|---|---|---|
| Z | NOR of all result bits | NOR tree | $\lceil \log_2 N \rceil$ levels |
| N | $R_{N-1}$ | wire | 0 |
| C | $C_{out}$ | wire | 0 |
| V | $c_{N-2} \oplus C_{out}$ | one XOR | 1 |
Practice Exercise
Problem 1. $A = 1100$ (unsigned 12, signed −4) and $B = 0101$ (5). Compute ADD and SUB with their flags, then decide from the SUB flags whether $A > B$ unsigned and whether $A > B$ signed.
Solution
ADD. $B’ = 0101$, carry-in 0.
| Bit | A | B' | Cin | Sum | Cout |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 1 | 1 | 0 | 0 | 1 |
| 3 | 1 | 0 | 1 | 0 | 1 |
Result $0001$, $c_3 = 1$, $C_{out} = 1$. Z = 0, N = 0, C = 1, V = 0. Unsigned 12 + 5 = 17 wrapped to 1, and C says so. Signed −4 + 5 = +1, correct, V = 0.
SUB. $B’ = 1010$, carry-in 1.
| Bit | A | B' | Cin | Sum | Cout |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 2 | 1 | 0 | 0 | 1 | 0 |
| 3 | 1 | 1 | 0 | 0 | 1 |
Result $0111$, $c_3 = 0$, $C_{out} = 1$. Z = 0, N = 0, C = 1, V = 1. Unsigned 12 − 5 = 7, correct, no borrow. Signed −4 − 5 = −9, which is below −8, so V = 1 and the pattern +7 is wrong.
Comparisons from the SUB flags. Unsigned $A > B$ needs C = 1 and Z = 0: yes, 12 > 5. Signed $A > B$ needs Z = 0 and N = V: N = 0, V = 1, so no, −4 is not greater than 5. The same two bit patterns compare opposite ways under the two interpretations, and the flags get both right.
Problem 2. Show that ARM’s GT condition, Z = 0 and N = V, is $\overline{Z} \cdot \overline{N \oplus V}$.
Solution
“Z = 0” is $\overline{Z}$. “N = V” means the XOR of N and V is 0, which is $\overline{N \oplus V}$, the XNOR. AND them together. In hardware that is an XNOR, an inverter and an AND: three gates to decide a signed greater-than branch.
That completes the ALU. Section 2.3 adds the two operations that do not fit in it comfortably: multiplication, which needs an array of adders, and shifting by an arbitrary amount, which needs a barrel shifter.