a two-bit predictor

Imagine a friend who is usually reliable about whether it will rain. If you switched your forecast the instant they were wrong even once, a single odd day would whipsaw you. Instead you wait for two surprises in a row before changing your mind. A two-bit predictor uses exactly this hysteresis for branches: it does not flip its prediction after a single wrong guess, so one unusual outcome does not derail an otherwise consistent pattern.

Concretely, each branch is associated with a 2-bit saturating counter holding one of four states: strongly not-taken (00), weakly not-taken (01), weakly taken (10), strongly taken (11). The prediction is simply the high bit: 0 means predict not-taken, 1 means predict taken. After each branch resolves, the counter increments toward 'taken' if the branch was taken and decrements toward 'not-taken' if it was not, saturating at the ends. Crucially, it takes two consecutive mispredictions to move from a strong state across to the opposite prediction. Contrast a one-bit predictor, which simply remembers the last outcome and therefore mispredicts twice on every loop (once at the start, once at the exit).

The two-bit scheme is the classic building block of branch prediction and a big jump over one bit. For a loop that is taken 99% of the time, the lone not-taken exit only nudges the counter to 'weakly taken' rather than flipping it, so the next entry to the loop is still predicted taken — saving the extra misprediction a one-bit predictor would suffer. Real high-end predictors are far more sophisticated (correlating, tournament, etc.), but they are almost all built on saturating counters like this, indexed by branch address and history.