Integer & Fixed-Point Math

Integer and fixed-point arithmetic

Scale into integers, order the operations so the intermediate cannot overflow, and round deliberately instead of letting C truncate toward zero. Multiply before dividing to keep the low bits, choose an intermediate type wide enough for the product, and add half the divisor before dividing to round to nearest. Division by a constant becomes a multiply and a shift; square roots and averages have exact integer forms. A float on a part without an FPU costs a library and hundreds of cycles for an answer integers could have given exactly.

Fixed point is just an integer with an agreed binary point. A value in Q16.16 is the real number times 65536, stored in an int32_t. Addition and subtraction work unchanged; multiplication doubles the number of fractional bits and needs a shift back; division needs a shift up first. Writing the Q format in the variable name is the cheapest bug prevention available, because the compiler cannot check it for you.

Order of operations decides both overflow and precision, and the two pull in opposite directions. Multiplying first keeps the low bits but risks overflowing the intermediate; dividing first is safe but throws away precision that cannot be recovered. The resolution is to multiply first in an intermediate type wide enough to hold the product - which usually means casting one operand up before the multiply, not after.

C's integer division truncates toward zero, which is a biased rounding mode: repeated use pulls an average steadily downward. Adding half the divisor before dividing gives round-to-nearest for positive values, and for signed values the correction has to depend on the sign. In a filter or an accumulator this is the difference between a stable value and a slow drift.

Patterns and when they apply

Q format fixed point

Fractional values with no FPU. Cost: A shift on multiply and divide. Avoid when: Mixing Q formats without renaming the variable.

widen-then-multiply

Scaling where the product exceeds the operand width. Cost: A wider intermediate. Avoid when: Casting the result instead of an operand.

add half before dividing

Round to nearest instead of toward zero. Cost: One addition. Avoid when: Applying it unchanged to negative values.

multiply-and-shift for division

Dividing by a compile-time constant. Cost: One multiply, one shift. Avoid when: Runtime divisors, where the reciprocal cannot be precomputed.

12-bit ADC count to millivolts

1. The relationship is mv = counts * vref / 4095.
2. Dividing first loses everything: counts/4095 is zero for every count below 4095.
3. Multiplying first: counts times vref for a 3300 mV reference reaches about 13.5 million, which needs more than 16 bits but fits an uint32_t.
4. Round to nearest: add 4095/2 before the divide.
5. Result: (counts * vref + 2047) / 4095, entirely in uint32_t.

An exact integer conversion with correct rounding, no library, and a provable absence of overflow.

Checklist

• What is the Q format, and is it in the name?
• Can the intermediate overflow at the extremes of the range?
• Does the division round or truncate?
• Is the divisor a compile-time constant?
• Would a float have pulled in a library on this part?

Easy - Scale an ADC Reading Without Floats

The conversion at the end of every ADC read: raw counts into millivolts, degrees, pascals or amps, on a part with no floating-point unit.

Convert a 12-bit ADC count to millivolts given a reference in millivolts, using integer arithmetic that neither overflows nor loses the low bits to truncation.

ADC counts to millivolts, exact and overflow-free

Converts a 12-bit ADC count to millivolts for a reference of vref_mv. Rounds to nearest. Requires counts <= 4095 and vref_mv <= 1000000; no intermediate overflows within that range.

#include <stdint.h>

#define ADC_FULL_SCALE 4095u

uint32_t adc_to_mv(uint16_t counts, uint32_t vref_mv) {
    /* Multiply FIRST: dividing first would give counts/4095 == 0 for
       every count below full scale, throwing the reading away entirely.
       counts <= 4095 and vref <= 1e6 gives a product under 4.1e9, which
       fits uint32_t - but only just, so the bound is part of the
       contract rather than a comment. */
    const uint32_t numerator = (uint32_t)counts * vref_mv;

    /* Add half the divisor to round to nearest instead of truncating
       toward zero, which otherwise biases every reading downward. */
    return (numerator + (ADC_FULL_SCALE / 2u)) / ADC_FULL_SCALE;
}

• Order decides everything. counts * vref / 4095 keeps the low bits; counts / 4095 * vref is zero for every input below full scale. The multiply has to come first, and the intermediate has to be wide enough to hold the product.
• The cast on counts is what widens the multiplication. Without it, uint16_t times uint32_t still promotes correctly here, but writing the cast makes the intended width explicit rather than depending on the reader knowing the promotion rules.
• Adding half the divisor before dividing converts C's truncation into round-to-nearest. Over a stream of samples the difference is not cosmetic: truncation biases the mean downward by half an LSB permanently, which in a calibrated instrument is an offset error.
• The input bounds are in the contract because the overflow-freedom depends on them. A vref of 1,000,000 mV is absurd physically but is the honest limit of the arithmetic, and stating it lets a reviewer check the claim rather than trust it.
• No float appears anywhere. On a Cortex-M0 the float version pulls in the soft-float library - kilobytes of flash - and takes hundreds of cycles for a result that is no more accurate than this one.

Cases the tests must cover

• counts = 0 → 0 mV
• counts = 4095, vref = 3300 → 3300 mV exactly
• counts = 2048, vref = 3300 → 1650 mV (exact value 1650.40)
• counts = 2, vref = 3300 → 2 mV, where truncation would have given 1
• counts = 1, vref = 3300 → 1 mV (rounds up from 0.806)
• Maximum inputs do not overflow uint32_t

How it gets written wrong

• Dividing before multiplying, which zeroes every reading below full scale.
• Omitting the rounding term, which biases the whole measurement chain downward.
• Dividing by 4096 instead of 4095 - a 12-bit converter's full scale is 4095 counts, and the off-by-one shows up as a gain error at the top of the range.

Medium - Divide by a Constant Without Dividing

Any per-sample or per-byte divide by a fixed constant: scaling to a unit, converting a rate, splitting a value into digits for a display.

Replace a division by a compile-time constant with a multiply and a shift, and show the result matches integer division across the whole input range.

Division by a constant as a multiply and a shift

Computes x / 10 for any uint32_t x using one 64-bit multiply and a shift, with a result identical to the division for the whole input range.

#include <stdint.h>

/* x / 10 == (x * M) >> S for a magic M and shift S. For divisor 10:
   M = 0xCCCCCCCD, S = 35. The pair comes from ceil(2^S / 10), chosen so
   the error stays below one for every uint32_t input. */
#define DIV10_MAGIC 0xCCCCCCCDu
#define DIV10_SHIFT 35u

uint32_t div_by_const(uint32_t x) {
    /* The product needs 64 bits: a 32x32 multiply overflows 32.
       On a part without a 64-bit multiply this compiles to a
       multiply-high instruction, which is still far cheaper than a
       hardware divide - and enormously cheaper than a software one. */
    return (uint32_t)(((uint64_t)x * DIV10_MAGIC) >> DIV10_SHIFT);
}

• Dividing by a constant is really multiplying by its reciprocal. Since integers cannot hold 1/10, the reciprocal is scaled up by 2^35, the multiply is done in 64 bits, and the shift scales it back down.
• The magic number is ceil(2^35 / 10) = 0xCCCCCCCD. Rounding up rather than down is what keeps the result correct: rounding down would make the answer one too small for some inputs, and the whole point is exactness across the entire range.
• This matters because many Cortex-M parts have no divide instruction at all. On those, a division by a variable is a software routine costing tens of cycles; this is a multiply and a shift. Compilers apply the transform automatically for constant divisors, which is exactly why dividing by a constant is cheap and dividing by a variable is not.
• The 64-bit intermediate is not optional. A 32-bit multiply would overflow and produce nonsense; on a 32-bit MCU the compiler emits a multiply-high instruction that keeps the top half, which is a single instruction on ARMv7-M.
• The technique only works for compile-time constants. For a runtime divisor the reciprocal would have to be computed first, which costs more than the division it replaces unless the same divisor is reused many times.

Cases the tests must cover

• x = 0 → 0
• x = 9 → 0, x = 10 → 1 (boundary correctness)
• x = 4294967295 → 429496729 (matches / 10 exactly)
• Result equals x / 10 for every value across the full range
• No 32-bit intermediate overflow occurs

How it gets written wrong

• Using a 32-bit intermediate, which overflows and produces a wrong answer for large inputs.
• Rounding the magic number down, which makes the result one too small for part of the range.
• Applying the technique to a runtime divisor, where computing the reciprocal costs more than dividing.

Easy - Integer Interpolation That Rounds

The inner step of every piecewise-linear calibration: interpolating between two table entries to convert a raw reading into a real one.

Interpolate between two table entries at a fractional position expressed as a numerator over a denominator, rounding to nearest rather than truncating toward zero.

Integer interpolation with correct rounding on both signs

Returns a + (b - a) * num / den, rounded to nearest. Handles negative deltas correctly. Requires den > 0 and num <= den; the caller owns those bounds.

#include <stdint.h>

int32_t lerp_i32(int32_t a, int32_t b, uint32_t num, uint32_t den) {
    if (den == 0u) {
        return a;
    }
    const int64_t delta = (int64_t)b - (int64_t)a;
    const int64_t scaled = delta * (int64_t)num;

    /* Round to nearest. C truncates toward zero, so the correction has
       to follow the sign of the value being divided - adding half
       unconditionally would round negatives the wrong way. */
    const int64_t half = (int64_t)(den / 2u);
    const int64_t rounded = (scaled >= 0)
        ? (scaled + half) / (int64_t)den
        : (scaled - half) / (int64_t)den;

    return (int32_t)((int64_t)a + rounded);
}

• The subtraction b - a is done in 64 bits because two int32_t values can differ by more than an int32_t holds: INT32_MAX minus INT32_MIN overflows immediately in 32-bit arithmetic, and that is undefined behaviour rather than a wrapped value.
• The rounding correction is sign-dependent, and this is the part most implementations get wrong. C's division truncates toward zero, so adding half a divisor rounds positives correctly and negatives in the wrong direction. Subtracting half for negatives restores symmetry.
• Interpolating as a + delta * num / den rather than (a * (den - num) + b * num) / den keeps the intermediate small and makes the endpoints exact: num = 0 gives exactly a, and num = den gives exactly b, with no rounding drift at the ends of each table segment.
• This is the inner loop of every piecewise-linear calibration on a device. Getting the rounding wrong biases every converted reading, and getting the width wrong makes it fail only at the extremes of the input range - which is where sensors sit when something is actually wrong.

Cases the tests must cover

• num = 0 returns exactly a; num = den returns exactly b
• Midpoint of 0 and 10 with num/den = 1/2 gives 5
• Midpoint of 0 and -10 gives -5, not -4 (sign-symmetric rounding)
• a = INT32_MIN, b = INT32_MAX does not overflow
• den = 0 returns a rather than dividing by zero

How it gets written wrong

• Computing b - a in 32 bits, which is undefined behaviour for far-apart endpoints.
• Adding half the divisor unconditionally, which rounds negative results away from nearest.
• Using the (a*(den-num) + b*num) form without widening, which overflows for large a and b.

Easy - Running Average Without Overflow

Smoothing a noisy sensor without storing its history - the standard one-line filter in front of a threshold comparison or a control input.

Maintain the mean of a stream of uint16_t samples in fixed point, without an accumulator that overflows and without drifting as the sample count grows.

Exponential running average in Q8 fixed point

Updates a Q24.8 running average with a new sample using a shift-based smoothing factor of 1/2^shift. Returns the new average in Q24.8. Bounded state: one word, forever.

#include <stdint.h>

/* avg_q8 holds the average scaled by 256 (Q24.8). shift selects the
   time constant: larger shift means slower, smoother tracking. */
uint32_t avg_update(uint32_t avg_q8, uint16_t sample, uint8_t shift) {
    if (shift > 15u) {
        shift = 15u;            /* keep the shift meaningful and defined */
    }
    const uint32_t sample_q8 = (uint32_t)sample << 8;

    /* avg += (sample - avg) >> shift, done so the subtraction cannot
       go negative in unsigned arithmetic. */
    if (sample_q8 >= avg_q8) {
        return avg_q8 + ((sample_q8 - avg_q8) >> shift);
    }
    return avg_q8 - ((avg_q8 - sample_q8) >> shift);
}

• The state is one word and never grows, which is the whole reason to use an exponential average rather than a windowed mean: a true moving average of the last N samples needs N samples in RAM, and this needs one.
• Working in Q24.8 keeps eight fractional bits, which is what stops the average from getting stuck. In pure integers, once the difference between sample and average is smaller than 2^shift the shift yields zero and the average never moves again - a real and frequently shipped bug.
• The branch on which value is larger is there because the arithmetic is unsigned. Computing sample_q8 - avg_q8 when the average is larger wraps to an enormous positive number, and the shift then adds a huge value instead of subtracting a small one.
• Clamping shift keeps the behaviour defined: a shift of 32 or more on a uint32_t is undefined in C, and a shift large enough to zero every update makes the filter silently stop tracking.
• The signed alternative - int32_t diff = sample - avg; avg += diff >> shift - is shorter but relies on arithmetic right shift of a negative value, which is implementation-defined. The unsigned form is portable.

Cases the tests must cover

• A constant input converges to that value and stays
• A step input approaches the new value geometrically
• The average moves even when the difference is under 2^shift (no stall)
• Rising and falling inputs track symmetrically
• shift above 15 is clamped rather than being undefined

How it gets written wrong

• Working in whole integers, so the filter stalls once the difference is smaller than the shift.
• Subtracting in unsigned arithmetic without checking which value is larger, which wraps.
• Letting shift reach or exceed the word width, which is undefined behaviour.

Medium - LFSR Jitter for Retry Backoff

Adding jitter to retry backoff so a fleet of devices that all lost connectivity at the same instant does not retry at the same instant.

Generate repeatable pseudo-random jitter with a maximal-length linear feedback shift register, so a fleet of devices does not retry in lockstep.

Maximal-length 16-bit LFSR for backoff jitter

Advances a 16-bit Galois LFSR one step. State must be non-zero; zero is a fixed point and is rejected by substituting a seed. Period is 65535 - every non-zero value appears once before repeating.

#include <stdint.h>

/* Taps 16,14,13,11 -> polynomial 0xB400 in Galois form. This tap set is
   one of the primitive polynomials for degree 16, which is what makes
   the period maximal (2^16 - 1) rather than some short cycle. */
#define LFSR_TAPS 0xB400u

uint16_t lfsr_next(uint16_t state) {
    if (state == 0u) {
        state = 0xACE1u;        /* zero is a fixed point: never enter it */
    }
    const uint16_t lsb = state & 1u;
    state >>= 1;
    if (lsb != 0u) {
        state ^= LFSR_TAPS;
    }
    return state;
}

• An LFSR is not a good general random number generator and is not trying to be. It is a few instructions, needs one word of state, and produces a repeatable sequence with a known period - which is exactly what retry jitter needs and what a cryptographic generator would be absurd overkill for.
• Zero is an absorbing state: shifting zero gives zero forever. Handling it by substituting a seed means a caller who forgot to initialise gets a working sequence rather than a generator that returns zero for the rest of the device's life.
• The tap set matters. An arbitrary choice of taps gives a short cycle - possibly only a few hundred values - so devices would repeat their jitter pattern quickly and resynchronise, which defeats the purpose. Primitive polynomials are what give the full 65535-value period.
• The intended use is exponential backoff: delay = base << attempt, then add lfsr_next(state) % spread. Without the jitter, a fleet of devices that all lost connectivity at the same moment retries at the same moment, and the server sees a thundering herd on every backoff boundary.
• Being repeatable is a feature here. Seeding from a device serial number gives each unit a different but reproducible sequence, so a field failure can be replayed exactly on the bench.

Cases the tests must cover

• State 0 is replaced rather than sticking at zero
• 65535 successive calls visit every non-zero value exactly once
• The 65536th call returns to the starting state
• The sequence is identical for identical seeds
• Different seeds produce different orderings of the same cycle

How it gets written wrong

• Allowing the state to reach zero, which stops the generator permanently.
• Choosing taps arbitrarily, which gives a short cycle and visible repetition.
• Using an LFSR where unpredictability matters - the entire state is recoverable from 16 consecutive output bits.

More in Embedded DSA

• The WorkbenchA complete embedded-first DSA course with theory, 80 challenges, complete C11 implementations, visual traces, mastery tracking, interview drills, and a constraint-driven firmware design arena.
• Arrays & WindowsTwo pointers, sliding windows, in-place compaction and streaming filters over sample buffers. Twelve problems with complete C11 solutions, complexity targets and edge-case tests.
• Search & LookupBinary search that actually terminates, lookup tables, perfect hashing and command dispatch. Eleven problems on getting a bounded answer out of a table without a heap allocation in sight.
• Lists, Pools & ArenasIntrusive linked lists, fixed-block pools, arena allocators and why malloc is banned in most firmware. Ten problems on owning memory with a bound you can prove before the board ships.
• Trees, Graphs & StateTries for command tables, union-find for connectivity, and state machines that cannot reach an undefined state. Nine problems on structures that encode relationships rather than sequences.
• Parsing & ProtocolsFraming, COBS, incremental parsers and adversarial input. Nine problems on decoding a byte stream from a hostile world without a buffer overflow or an unbounded loop.
• Linked ListsEvery list variant, written for embedded C rather than for a whiteboard: singly and doubly linked, circular lists and sentinels that delete the boundary cases, the intrusive form kernels and firmware actually use, static pools and free lists for systems without malloc, reversal and cycle detection, and an honest account of when an array is the better answer.
• Sorting Under ConstraintWhich sort survives a 512-byte stack and a fixed deadline. Insertion sort for small nearly-sorted windows, heapsort when the worst case must be provable, counting sort for byte keys, and a bounded-depth quicksort - six problems with complete C11 solutions.
• Heaps & SchedulingBinary heaps as timer wheels and task schedulers, and wrap-safe time comparison - the bug that only shows up 49 days after the board is deployed. Eight problems with complete solutions.
• Stacks, Queues & RingsThe ring buffer and the SPSC queue: the two structures every firmware project actually ships. Ownership between an ISR and a main loop, overflow policy, and why the full/empty test is where the bugs are.
• Bits & BytesRegister fields, bit reversal, parity, endianness and portable packet decoding, without invoking undefined behaviour. Seven problems with complete C11 solutions and a step-by-step trace for each.
• Firmware CapstonesSix full-system problems: DMA ownership, wear-levelled persistence, crash-safe logging and proving a design meets its RAM and WCET budget. This is where every earlier stage gets used at once.