algorithm - 使用位旋转截断整数

Question

有没有一种方法可以使用位旋转来“截断”一个整数，就好像它被地板分割然后再相乘一样，如下所示:

z = floor(x / y) * y

我知道如果 y 是 2 的幂，就可以这样做，例如:

z = floor(x / 4) * 4 == x & ~3

但是当 y 是一些一般的正整数时，人们使用什么技巧呢？

Answer 1

对于每个人 y ，有一个操作序列(加法、减法和二进制移位)除以 x通过 y比 (x86) 除法指令更快。然而，找到该序列并不简单，必须提前完成(当您除以相同的 y 很多 时可行)。

一个简单的例子:划分任意uint32 x通过 3，我们可以改为计算 x * M在 uint64输入并将其右移 33 位，其中 M是一个魔法常数，等于 2³³/3 四舍五入向上。

以下代码 (C) 随机尝试 20 uint32值与上述算法并检查结果是否等于仅除以 3:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main ()
{
    int step;
    unsigned x, y1, y2;
    unsigned const M = (1ULL << 33) / 3 + 1;
    srand (time (NULL));
    for (step = 0; step < 20; step++)
    {
        x = (rand () << 30) | (rand () << 15) | rand ();
        y1 = x / 3;
        y2 = (x * 1ULL * M) >> 33;
        printf ("%10u %10u %10u %s\n", x, y1, y2, y1 == y2 ? "true" : "false");
    }
    return 0;
}

有关更多信息，请参阅《Hacker's Delight》一书，以及免费提供的增补内容 - 第 10 章:hackersdelight.org/divcMore.pdf .