---
title: Arithmetic and Logic
module: Machine-Level Programming
moduleNumber: 1
lessonNumber: 3
order: 103
summary: >
  The ALU instructions that compute on register and memory values: add, sub, and
  imul; the unary inc/dec/neg/not; the shifts sal/shr/sar; the bitwise and/or/xor;
  and lea reused as a fast arithmetic trick. Each binary operation also sets the
  condition-code flags CF, ZF, SF, and OF, which cmp and test compute without
  keeping a result.
topics: [Machine-Level Programming]
sources:
  - book: Bryant & O'Hallaron
    ref: "CS:APP — §3.5 Arithmetic and Logical Operations; §3.6.1 Condition Codes"
---

With operands in place, the machine computes. x86-64's integer arithmetic and
logic instructions are a compact set: a few binary operations, a few unary ones,
the shifts, and the bitwise logicals. Two facts make them more than a table to
memorize. First, `lea` from the previous lesson doubles as an arithmetic
instruction. Second, almost every arithmetic instruction quietly sets the
**condition-code flags** as a side effect, and those flags are what the conditional
jumps of the next lesson read.

## Binary and unary operations

The binary operations take two operands and write the result to the destination,
following the AT&T source-then-destination order. The destination accumulates: `D`
becomes `D op S`, **not** `S op D`. This matters for the non-commutative `sub`.

| Instruction | Effect |
| --- | --- |
| `addq S, D` | $D \leftarrow D + S$ |
| `subq S, D` | $D \leftarrow D - S$ |
| `imulq S, D` | $D \leftarrow D \cdot S$ |
| `andq S, D` | $D \leftarrow D\ \&\ S$ (bitwise AND) |
| `orq S, D` | $D \leftarrow D \mathbin{\vert} S$ (bitwise OR) |
| `xorq S, D` | $D \leftarrow D \oplus S$ (bitwise XOR) |

The operand order is worth stating plainly: `subq %rax, %rbx` computes
$\mathtt{rbx} \leftarrow \mathtt{rbx} - \mathtt{rax}$, subtracting the source from
the destination. Reading it as "rax minus rbx" inverts the sign of every program
you analyze.

The unary operations take a single operand that is both source and destination.

| Instruction | Effect |
| --- | --- |
| `incq D` | $D \leftarrow D + 1$ |
| `decq D` | $D \leftarrow D - 1$ |
| `negq D` | $D \leftarrow -D$ |
| `notq D` | $D \leftarrow\ \mathord{\sim} D$ (bitwise complement) |

```asm [arith.s]
# long arith(long x, long y): x in %rdi, y in %rsi
addq    %rsi, %rdi        # rdi = x + y
imulq   $3, %rdi          # rdi = 3*(x+y)
negq    %rdi              # rdi = -(3*(x+y))
movq    %rdi, %rax        # result to the return register
ret
```

By convention a procedure's result comes back in `%rax`, hence the final `movq`;
the rule is made precise in the lesson on
[procedures](/computer-architecture/machine-level-x86-64/procedures).

## lea as a fast arithmetic trick

The `lea` instruction from
[data movement](/computer-architecture/machine-level-x86-64/data-movement)
computes `Imm + Rb + Ri·S` and stores it. Used on plain integers rather than
addresses, it is a three-input adder with a built-in small multiplier, and it does
**not** disturb the condition codes — a property compilers exploit to compute
intermediate values without clobbering flags a later branch depends on.

$$
% caption: leaq 6(%rdi,%rsi,4), %rax as arithmetic: it evaluates the address
% caption: formula 6 + rdi + 4*rsi and stores the number, touching no memory and
% caption: setting no flags.
\begin{tikzpicture}[font=\footnotesize, >=stealth,
  box/.style={draw, minimum width=14mm, minimum height=8mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (rsi) at (0,0)   {$\mathtt{\%rsi}$};
  \node[box] (s4)  at (2.4,0) {x 4};
  \node[box] (rdi) at (0,-1.6) {$\mathtt{\%rdi}$};
  \node[box] (imm) at (0,-3.2) {$+\,6$};
  \node[box, draw=acc, thick] (sum) at (5.4,-1.6) {$+$};
  \node[box, draw=acc, thick] (out) at (8.0,-1.6) {$\mathtt{\%rax}$};
  \draw[->, thick] (rsi) -- (s4);
  \draw[->, thick] (s4.east) -- ([yshift=4mm]sum.west);
  \draw[->, thick] (rdi.east) -- (sum.west);
  \draw[->, thick] (imm.east) -- ([yshift=-4mm]sum.west);
  \draw[->, thick] (sum) -- (out) node[midway, above, font=\scriptsize, text=acc] {store};
  \node[font=\scriptsize, align=center] at (5.4,-3.0) {$6 + \mathtt{rdi} + 4\,\mathtt{rsi}$};
\end{tikzpicture}
$$

So `leaq (%rdi,%rdi,2), %rax` triples a number ($x + 2x$), `leaq (,%rdi,8), %rax`
multiplies by 8, and `leaq 1(%rdi,%rsi), %rax` computes $x + y + 1$ — each in one
flag-preserving instruction.

A compiler chains these to avoid a general multiply entirely. The function
`long f(long x) { return 7 * x; }` has a constant multiplier, and $7x = 8x - x$, so
gcc computes it without `imul`:

```asm [times7.s]
# long f(long x): return 7 * x;  x in %rdi
leaq    0(,%rdi,8), %rax   # rax = 8*x   (scale-8, no base)
subq    %rdi, %rax         # rax = 8*x - x = 7*x
ret
```

Trace it with `x = 5`. The `leaq` computes $8 \cdot 5 = 40$ into `%rax`; the `subq`
then does $40 - 5 = 35 = 7 \cdot 5$, the answer. Two cheap instructions replaced a
multiply, and the `lea` never touched the flags in between. The compiler picks this
**strength reduction** whenever the constant factors into small shifts and adds; a
factor like $10 = 8 + 2$ becomes `leaq (%rdi,%rdi,4), %rax` (that is $5x$) followed by
`addq %rax, %rax` (doubling to $10x$). Reading such a pair backward — "scale by 8,
subtract one $x$" — is how you recover the constant the source multiplied by.

## Shifts

The shift instructions move the bits of the destination left or right by a count
given either as an immediate or in the single-byte register `%cl`. Left and right
each come in the flavors the two's-complement representation demands.

- `sal k, D` / `shl k, D` — **shift left** by `k`, filling with zeros. The two
  mnemonics are identical; left shift by `k` multiplies by $2^k$.
- `shr k, D` — **logical** shift right, filling the vacated high bits with zeros.
  This is the right shift for **unsigned** values.
- `sar k, D` — **arithmetic** shift right, filling the high bits with copies of the
  sign bit. This is the right shift for **signed** values, preserving the sign.

$$
% caption: Right shifts of the byte 1011 0010 by 2. Logical shr fills with zeros;
% caption: arithmetic sar replicates the sign bit (1 here), preserving sign.
\begin{tikzpicture}[font=\footnotesize,
  bit/.style={draw, minimum size=6mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  % original
  \node[anchor=east] at (-0.4,1.4) {original};
  \foreach \i/\v in {0/1, 1/0, 2/1, 3/1, 4/0, 5/0, 6/1, 7/0}
    \node[bit] at (\i*0.7,1.4) {\v};
  % shr by 2 (logical, fill 0)
  \node[anchor=east] at (-0.4,0.4) {\texttt{shr} 2};
  \foreach \i/\v in {2/1, 3/0, 4/1, 5/1, 6/0, 7/0}
    \node[bit] at (\i*0.7,0.4) {\v};
  \foreach \i in {0,1} \node[bit, draw=acc, text=acc] at (\i*0.7,0.4) {0};
  % sar by 2 (arithmetic, fill sign=1)
  \node[anchor=east] at (-0.4,-0.6) {\texttt{sar} 2};
  \foreach \i/\v in {2/1, 3/0, 4/1, 5/1, 6/0, 7/0}
    \node[bit] at (\i*0.7,-0.6) {\v};
  \foreach \i in {0,1} \node[bit, draw=acc, text=acc] at (\i*0.7,-0.6) {1};
\end{tikzpicture}
$$

A variable count has a fixed home: the shift instructions read it only
from the single-byte register `%cl`, never from an arbitrary register. So a shift
by a computed amount first moves that amount into `%cl`, as in `movb %r8b, %cl`
then `shlq %cl, %rax`. The immediate form `shlq $3, %rax` is the other option, used
when the count is a constant.

The hardware then consults only the **low bits** of the count, masking it to the
operand width: a 32-bit shift uses `%cl` mod 32 (its low 5 bits), a 64-bit shift
uses `%cl` mod 64 (its low 6 bits). A count of 33 on a 32-bit value therefore
shifts by 1, not 33, and never clears the whole register the way a naive reading
would suggest. This masking is why a shift amount is always in range.

A quick trace shows the masking in action. Suppose
`%cl` holds `33` and the instruction is `shll %cl, %eax`, a 32-bit shift. The
hardware keeps only the low 5 bits of the count, and $33 = \mathtt{0b100001}$, whose
low five bits are `00001` — a count of **1**. So `%eax` shifts left by one, doubling,
not by 33 (which would clear it to zero). The same `%cl = 33` fed to a 64-bit
`shlq %cl, %rax` keeps the low 6 bits, `100001`, again a count of 1. The width of
the operand decides how many count bits survive: 5 bits for 32-bit shifts, 6 for
64-bit, so a shift amount is always in range and can never blank a register the way
a naive "shift by 33" would.

The signed/unsigned split is what makes C's `>>` compile to `sar` for `int` and
`shr` for `unsigned`.

Left shift is simpler: every bit slides toward the high end and zeros
flow in at the bottom, which multiplies the value by $2^k$. This is why a compiler
turns `x * 8` into `sal $3, x` — a shift is far cheaper than a multiply.

$$
% caption: A left shift by 1. Each bit moves one place toward the high end, a zero
% caption: enters at the low end, and the top bit falls off; the value doubles, so
% caption: sal $1 is multiply-by-two.
\begin{tikzpicture}[font=\footnotesize, >=stealth,
  bit/.style={draw, minimum size=6mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[anchor=east, font=\scriptsize] at (-0.4,1.2) {before};
  \foreach \i/\v in {0/0, 1/0, 2/1, 3/1, 4/0, 5/1, 6/0, 7/1}
    \node[bit] at (\i*0.7,1.2) {\v};
  \node[anchor=east, font=\footnotesize] at (-0.4,0.0) {\texttt{sal} 1};
  \foreach \i/\v in {0/0, 1/1, 2/1, 3/0, 4/1, 5/0, 6/1}
    \node[bit] at (\i*0.7,0.0) {\v};
  \node[bit, draw=acc, text=acc] at (7*0.7,0.0) {0};
  % falling top bit
  \draw[->, acc] (-0.15,1.2) -- (-0.15,0.5) -- (0.2,0.5);
  \node[text=acc, font=\scriptsize, anchor=east] at (-0.45,0.55) {drops};
\end{tikzpicture}
$$

## Condition codes

Beyond their named registers, the processor keeps a few single-bit **condition-code
flags** that record properties of the most recent arithmetic or logical result.
The four that matter here are set as a side effect of nearly every ALU
instruction.[^flags]

> **Definition (Condition codes).** Four flag bits describing the last ALU result:
> **CF** (carry flag), set when an unsigned operation carried out of the most
> significant bit; **ZF** (zero flag), set when the result was zero; **SF** (sign
> flag), set when the result's most significant bit was 1 (it is negative as a
> signed value); and **OF** (overflow flag), set when a signed operation overflowed
> the representable range.

$$
% caption: The four ALU condition-code flags. CF watches unsigned carry-out, ZF
% caption: whether the result is zero, SF the sign bit, OF signed overflow.
\begin{tikzpicture}[font=\footnotesize,
  flg/.style={draw, minimum width=12mm, minimum height=8mm, inner sep=1pt, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[flg] (cf) at (0,0)   {\texttt{CF}};
  \node[flg] (zf) at (1.8,0) {\texttt{ZF}};
  \node[flg] (sf) at (3.6,0) {\texttt{SF}};
  \node[flg] (of) at (5.4,0) {\texttt{OF}};
  \node[font=\scriptsize, align=center] at (0,-1.0)   {unsigned\\carry};
  \node[font=\scriptsize, align=center] at (1.8,-1.0) {result\\$=0$};
  \node[font=\scriptsize, align=center] at (3.6,-1.0) {sign\\bit};
  \node[font=\scriptsize, align=center] at (5.4,-1.0) {signed\\overf\/low};
\end{tikzpicture}
$$

A worked case shows all four flags at once and why signed and unsigned overflow are
different events. Work in a single byte (8 bits) to keep the numbers small, and add
`0x50 + 0x50` (decimal $80 + 80$).

$$
% caption: addb $0x50, %al with %al = 0x50. The 8-bit result 0xA0 sets no carry
% caption: (CF=0) but does set SF (top bit 1) and OF (two positives gave a negative).
% caption: As unsigned this is 160, correct; as signed it is -96, an overflow.
\begin{tikzpicture}[font=\footnotesize, >=stealth,
  cell/.style={draw, minimum width=22mm, minimum height=6.5mm, inner sep=2pt, align=center},
  flg/.style={draw, minimum width=9mm, minimum height=6.5mm, inner sep=0pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[cell] (a) at (0,0.8) {$\mathtt{0x50} = 80$};
  \node[cell] (b) at (0,0.0) {$+\ \mathtt{0x50} = 80$};
  \node[cell, draw=acc, thick] (r) at (0,-0.8) {$\mathtt{0xA0}$};
  \draw[acc] (-1.25,-0.45) -- (1.25,-0.45);
  % flags
  \node[flg] (cf) at (3.4,0.7)  {CF=0};
  \node[flg] (zf) at (4.6,0.7)  {ZF=0};
  \node[flg, draw=acc, text=acc] (sf) at (3.4,-0.3) {SF=1};
  \node[flg, draw=acc, text=acc] (of) at (4.6,-0.3) {OF=1};
  \draw[->, thick] (r.east) -- (2.4,-0.8);
  % interpretations
  \node[anchor=west, font=\scriptsize] at (6.0,0.4) {unsigned: $160$ (in range)};
  \node[anchor=west, font=\scriptsize, text=acc] at (6.0,-0.4) {signed: $\text{-}96$ (overf\/low)};
\end{tikzpicture}
$$

Read the result three ways. The bit pattern is `0xA0 = 1010 0000`. There was no
carry _out_ of the top bit, so `CF = 0`: as an **unsigned** sum, $80 + 80 = 160$
fits in a byte and is correct. But the top bit is now 1, so `SF = 1`, and two
positive signed operands produced a negative-looking result — the definition of
signed overflow — so `OF = 1`: as a **signed** sum, $80 + 80$ should be $160$, which
does not fit in the signed byte range $[-128, 127]$, and the value reads as $-96$.
The same addition on the same bits produces two different overflow verdicts, which is
why the conditional jumps split into signed and unsigned families in the
[next lesson](/computer-architecture/machine-level-x86-64/control-flow). The
processor sets every flag on every add and lets the branch pick which ones matter.

Two design points keep the flags useful. First, `lea` does **not** set flags
(noted above), nor do plain `mov` instructions. Second, the instructions that do
set them are not uniform about it: `add`, `sub`, the logicals, `neg`, and the
shifts all update the flags, `not` sets none at all, and `inc`/`dec` set every
flag _except_ CF, which they leave untouched — a classic x86 quirk that lets a
loop counter step without destroying a carry. So a compiler can compute an
address with `lea`, then test a value, and trust the flags it cares about to
survive.

## cmp and test

Two instructions exist purely to **set flags without keeping a result** — exactly
what a conditional branch needs, since the question is how two values compare, not
what their difference is.

- `cmpq S2, S1` computes $S_1 - S_2$, sets the flags accordingly, and **discards**
  the difference. Note the operand order: the flags describe $S_1 - S_2$, so
  `cmpq %rsi, %rdi` sets ZF when $\mathtt{rdi} = \mathtt{rsi}$ and SF/OF as if you
  had subtracted `%rsi` from `%rdi`.
- `testq S2, S1` computes $S_1\ \&\ S_2$, sets the flags, and discards the AND. The
  common idiom `testq %rax, %rax` sets ZF exactly when `%rax` is zero and SF when
  it is negative — a register sign/zero check costing no scratch register.

$$
% caption: cmp is sub with the result thrown away. It subtracts source from
% caption: destination only to set the four flags; both operands keep their values,
% caption: so it compares without disturbing either, priming the next branch.
\begin{tikzpicture}[font=\footnotesize, >=stealth,
  box/.style={draw, minimum width=14mm, minimum height=8mm, align=center},
  flg/.style={draw, minimum width=8mm, minimum height=7mm, inner sep=0pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (s1) at (0,0.6)  {$\mathtt{\%rdi}$};
  \node[box] (s2) at (0,-0.6) {$\mathtt{\%rsi}$};
  \node[box, draw=acc, thick] (alu) at (3.0,0) {$S_1$ - $S_2$};
  \draw[->, thick] (s1.east) -- (alu.north west);
  \draw[->, thick] (s2.east) -- (alu.south west);
  % flags out
  \node[flg, draw=acc, fill=acc!8] (cf) at (6.0,0.9) {CF};
  \node[flg, draw=acc, fill=acc!8] (zf) at (6.9,0.9) {ZF};
  \node[flg, draw=acc, fill=acc!8] (sf) at (6.0,0.0) {SF};
  \node[flg, draw=acc, fill=acc!8] (of) at (6.9,0.0) {OF};
  \draw[->, thick, acc] (alu.east) -- (5.5,0.45);
  % discarded result
  \node[font=\scriptsize, align=center] at (5.2,-1.1) {result\\discarded};
  \draw[->, thick] (alu.south) |- (4.4,-1.1);
\end{tikzpicture}
$$

```asm [cmp.s]
# branch on whether x < y, x in %rdi, y in %rsi (signed)
cmpq    %rsi, %rdi        # flags describe rdi - rsi
jl      .Lless            # jump if x < y  (reads SF, OF)
```

The flags `cmp` and `test` deposit are read by the conditional jumps and set
instructions, which translate "the flags say `%rdi < %rsi`" into a taken branch.
That translation is the whole of the next lesson on
[control flow](/computer-architecture/machine-level-x86-64/control-flow).

## The operations one register cannot hold

The two-operand `imulq S, D` above keeps only the low 64 bits of a 64-by-64-bit
product, which is all a C `long` multiply needs. But the true product of two 64-bit
numbers is up to 128 bits, and CS:APP notes in passing that x86-64 has one-operand
forms — `mulq S` (unsigned) and `imulq S` (signed) — that produce the **full**
double-width result, splitting it across `%rdx:%rax` (high half in `%rdx`, low in
`%rax`). Division is the mirror image: `idivq S` takes a 128-bit dividend in
`%rdx:%rax` and leaves the quotient in `%rax` and the remainder in `%rdx`, which is
why signed division is always preceded by `cqto`, an instruction whose only job is to
sign-extend `%rax` into `%rdx` so the dividend is a proper 128-bit value. These
fixed-register operands are a rare place where x86-64 pins specific registers, a
direct inheritance from the 8086's accumulator model.[^muldiv]

The modern chapter the textbook predates is the **BMI** (Bit Manipulation
Instruction) extensions Intel and AMD added around 2013. They turn common bit idioms
that once took several instructions into one: `andn` computes `~x & y` without a
separate `not`; `blsr` clears the lowest set bit; `tzcnt` and `lzcnt` count trailing
and leading zeros directly, which compilers emit for C's `__builtin_ctz` and
`__builtin_clz`; and `pdep`/`pext` scatter and gather bits under a mask. A compiler
targeting a recent `-march` will replace a hand-rolled bit-twiddle loop with one of
these, so a shift-and-mask sequence you expect may appear as a single unfamiliar
mnemonic. They obey the same operand grammar as the classic ALU instructions, only
with more specialized semantics.[^bmi]

> **Takeaway.** The ALU set is small: `add`/`sub`/`imul`, the unary
> `inc`/`dec`/`neg`/`not`, the shifts `sal`/`shr`/`sar` (logical vs arithmetic for
> unsigned vs signed), and `and`/`or`/`xor`. `lea` computes `Imm + Rb + Ri·S`
> without setting flags. Binary ops set **CF/ZF/SF/OF** as a side effect; `cmp` and
> `test` set them from a subtraction or an AND while discarding the result, priming
> the next branch.

[^flags]: **Bryant & O'Hallaron**, _CS:APP_, §3.6.1 — Condition Codes: CF, ZF, SF, and OF are set by arithmetic and logical instructions; `lea` and `mov` leave them unchanged, and `cmp`/`test` set them without storing a result.
[^muldiv]: **Bryant & O'Hallaron**, _CS:APP_, §3.5.5 — Special Arithmetic Operations: the one-operand `mulq`/`imulq` producing a 128-bit product in `%rdx:%rax`, and `idivq` dividing the `%rdx:%rax` pair with `cqto` sign-extending the dividend.
[^bmi]: **Intel**, _Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 1_ (2023), §14.3 and the BMI1/BMI2 instruction listings — `andn`, `blsr`, `tzcnt`, `lzcnt`, `pdep`, and `pext` as single-instruction replacements for common bit-manipulation sequences.