strength reduction

Some operations are cheaper for a processor than others: shifting bits is faster than a general multiply, adding is faster than multiplying, and multiplying is faster than dividing. Strength reduction is the optimization that swaps an expensive operation for a cheaper one that produces the same result — it 'reduces the strength' of the operation.

There are two common flavors. The simple, local kind rewrites a single operation: multiplying an unsigned value by 8 becomes a left shift by 3 (x * 8 becomes x << 3), since shifting by 3 is the same as multiplying by 2 to the power 3; dividing an unsigned value by a power of two becomes a right shift; multiplying by a constant can become a couple of shifts and adds. The more powerful kind targets loops, where a variable grows by a fixed step each iteration (an induction variable). If a loop computes i * 4 each time through, the compiler can instead keep a running value and add 4 per iteration, replacing a multiply in the loop body with an addition — a big win because it fires every iteration.

It matters because it directly cuts the cost of hot inner loops, especially address arithmetic (computing base + i * element_size for array access is a textbook target). A caveat for the signed-versus-unsigned distinction that systems programmers care about: replacing multiply or divide by a shift is only valid when it gives identical results. For unsigned values, dividing by a power of two equals a right shift cleanly. For SIGNED values it does not — a signed divide rounds toward zero while an arithmetic right shift rounds toward negative infinity for negatives — so the compiler must emit extra correction or refuse the simple shift. The compiler handles this correctly; the lesson is that 'just shift instead of divide' is only safe by hand for unsigned types.