Skip to content
BetterDL

Number of flip-flops needed

Also called: flip-flops needed, minimum number of flip-flops, number of flip-flops, ceiling of log2 N

The fewest flip-flops that can give N distinct states with binary encoding: the smallest n with 2ⁿ ≥ N, written ⌈log₂ N⌉.

Every state of a counter or finite state machine needs its own bit pattern. n flip-flops give 2ⁿ patterns, so N states need the smallest n with

2ⁿ ≥ N, that is, n = ⌈log₂ N⌉.

The ⌈ ⌉ means round up. Two flip-flops give only 4 patterns, so even 5 states force a third flip-flop.

The safest way avoids logarithms: list powers of 2 (2, 4, 8, 16, 32, 64, 128, 256, …) and stop at the first one that is at least N. Its exponent is the answer. Whatever is left over, 2ⁿ − N, becomes unused states.

That's the minimum, for binary encoding. Other encodings trade flip-flops for simpler logic:

Worked examples

Example

A few quick cases

Find the fewest flip-flops for each number of states.

  1. 1.

    N = 8: 2³ = 8 exactly → 3 flip-flops, none unused.

  2. 2.

    N = 9: 8 < 9 ≤ 16 → 4 flip-flops, 7 unused. Crossing a power of 2 costs a whole flip-flop.

  3. 3.

    N = 60 (seconds): 32 < 60 ≤ 64 → 6 flip-flops, 4 unused.

  4. 4.

    N = 1000: 512 < 1000 ≤ 1024 → 10 flip-flops.

Example

A state machine with 5 states

log₂ 5 ≈ 2.32. How many flip-flops does a 5-state FSM need with binary encoding? With one-hot?

  1. 1.

    Round up: 3 flip-flops (2 would give only 4 codes).

  2. 2.

    Check: 2³ = 8 ≥ 5 ✓, leaving 3 unused codes.

  3. 3.

    One-hot: one flip-flop per state, so 5.

Common mistakes

  • Rounding log₂ N to the nearest whole number instead of up. 5 states need 3 flip-flops, not 2.

  • Using the maximum count instead of the number of states. Counting 0 to 8 is 9 states and needs 4 flip-flops.

  • Answering N (one per state) when the question assumes binary encoding.

Practice Number of flip-flops needed

Interactive questions with instant feedback and a worked solution for every wrong answer.

Counters lesson full course

And 1 more in the Counters lesson.

Practice exams

Related terms

Learn it step by step

Number of flip-flops needed is taught in Counters and Finite State Machines.

Counters →Finite State Machines →

All terms