Rounding integer division by multiply-and-shift

Question

I learned about this trick the other day by inspecting the machine code generated by gcc. Dividing an integer a by a constant b can be optimized as follows:

x = a / b
x = a * (1 / b)
x = (a * (((1 << n) / b) + 1)) >> n

The reciprocal can be evaluated at compile-time, resulting in a multiply-and-shift operation that is more efficient than division.

c = ((1 << n) / b) + 1
x = (a * c) >> n

Now this has the same effect as plain integer division, it truncates the result (rounding towards zero). Is it possible to modify this algorithm to round towards the nearest value instead?

You don't need to care about that. Just do a normal division, with adjustments before or after for rounding. See Rounding integer division (instead of truncating), Fast ceiling of an integer division in C / C++ — phuclv
I'm writing a vector division routine using MMX, so I do care. — user5434231
Note that your trick doesn't work in many cases: e.g., suppose a = 3, b = 3. Let's pick n = 32 (for the sake of argument, but actually any n will do here). Then your shortcut gives a result x = 0 instead of the expected x = 1. There are many similar cases. So the statement "this has the same effect as plain integer division" isn't true. — Mark Dickinson

user5434231 user5434231 · Accepted Answer · 2018-09-04T17:15:52

I came up with:

c = (1 << n) / b
d = a * c
x = ((d >> (n - 1)) & 1) + (d >> n)

Does the trick, but I wonder if there are more efficient methods.

edit: I posed the same question on reddit and got a better answer: https://www.reddit.com/r/AskProgramming/comments/9cx9dl/rounding_integer_division_by_multiplyandshift/

c = ((1 << n) + b - 1) / b;
x = (((a * c) >> (n - 1)) + 1) >> 1

One more shift can be removed by defining another constant:

e = 1 << (n - 1)
x = (a * c + e) >> 1

Rounding integer division by multiply-and-shift

1 Answers