c++ - 重复整数除以运行时常量值

Question

在我的程序中的某个时刻，我计算了一个整数除数 d。从那时起，d 将保持不变。

稍后在代码中，我将多次除以 d - 执行整数除法，因为 d 的值不是编译时已知的常量。

鉴于整数除法与其他类型的整数算术相比是一个相对较慢的过程，我想对其进行优化。是否有一些替代格式可以存储 d 以使除法过程执行得更快？也许是某种形式的倒数？

我不需要 d 的值来做其他任何事情。

d 的值是任何 64 位整数，但通常非常适合 32 位。

Answer 1

为此有一个库— libdivide :

libdivide is an open source library for optimizing integer division

libdivide allows you to replace expensive integer divides with comparatively cheap multiplication and bitshifts. Compilers usually do this, but only when the divisor is known at compile time. libdivide allows you to take advantage of it at runtime. The result is that integer division can become faster - a lot faster. Furthermore, libdivide allows you to divide an SSE2 vector by a runtime constant, which is especially nice because SSE2 has no integer division instructions!

libdivide is free and open source with a permissive license. The name "libdivide" is a bit of a joke, as there is no library per se: the code is packaged entirely as a single header file, with both a C and a C++ API.

您可以在 blog 上了解它背后的算法。 ;例如，这个 entry .

基本上，它背后的算法与编译器用来优化除以常数的算法相同，只是它允许在运行时完成这些强度降低优化。

注意:您可以创建更快的 libdivide 版本。这个想法是，对于每个除数，您总是可以创建一个三元组 (mul/add/shift)，所以这个表达式给出了结果: (num*mul+add)>>shift(这里的乘法是宽乘法)。有趣的是，这种方法可以在多个微基准测试中击败编译器版本的常量除法!

---

这是我的实现(这不是开箱即用的编译，但可以看到通用算法):

struct Divider_u32 {
    u32 mul;
    u32 add;
    s32 shift;

    void set(u32 divider);
};

void Divider_u32::set(u32 divider) {
    s32 l = indexOfMostSignificantBit(divider);
    if (divider&(divider-1)) {
        u64 m = static_cast<u64>(1)<<(l+32);
        mul = static_cast<u32>(m/divider);

        u32 rem = static_cast<u32>(m)-mul*divider;
        u32 e = divider-rem;

        if (e<static_cast<u32>(1)<<l) {
            mul++;
            add = 0;
        } else {
            add = mul;
        }
        shift = l;
    } else {
        if (divider==1) {
            mul = 0xffffffff;
            add = 0xffffffff;
            shift = 0;
        } else {
            mul = 0x80000000;
            add = 0;
            shift = l-1;
        }
    }
}

u32 operator/(u32 v, const Divider_u32 &div) {
    u32 t = static_cast<u32>((static_cast<u64>(v)*div.mul+div.add)>>32)>>div.shift;

    return t;
}