使用位旋转截断整数

Question

有没有一种方法可以使用位旋转 "truncate" 一个整数，就好像它被除以然后再相乘一样，如：

z = floor(x / y) * y

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

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

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

Answer 1

这适用于 2 的幂的原因是二进制表示的工作方式。除以 2（或 2 的幂）与位移相同。向右移动然后向左移动相同的量与您所说的地板分隔相同。

考虑一个任意的二进制数：110101010111。如果你将它向右移动 3 次（除以 8），然后再返回，它会变成 110101010000，这与 111111111000 相同。现在让我们考虑除以（十进制）数字 16 的 3：从 10000 开始。除以 3（不是移位！）将是 5 (101)，再次乘以 3 是 15 (1111)。没有位移可以做到这一点。

Answer 2

显而易见的事情是转换为您尝试使用的任何基数，然后基本上使最后一位数字为 0。（或者，如果您正在使用 k 次方，则将最后 k 位数字设为 0 ).但是，您询问了位（base-2）操作。事实证明，对于任何所需的基数 B（至少是奇数），您可以想出一个二进制数，这样对于任何 M，基数 B 中的前 M 位都是您想要的任何数字。因此，您怎么能可能有一个通用的方法来满足您的需求（奇数基），它只适用于位（二进制）？至少它可能比简单地将您的数字转换为您想要的基数并将最后一位数字设置为 0 然后转换回自然的 base-2 整数表示要复杂得多。

Answer 3

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

一个简单的例子：要将任意的uint32x除以3，我们可以改为计算uint64类型的x * M并将其向右移动33位，其中 M 是一个魔术常数，等于 2³³ / 3 舍入 up.

以下代码 (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。

使用位旋转截断整数

Truncate integer using bit twiddling

algorithm

math

integer

bit-manipulation