21

处理器中的除法需要很多时间，所以我想问一下如何以最快的方式检查数字是否可以被其他数字整除，在我的情况下，我需要检查数字是否可以被 15 整除。

此外，我一直在浏览网页并找到有趣的方法来检查数字是否可以被某个数字整除，但我正在寻找快速选项。

注意：由于除法需要很多时间，我正在寻找没有/and的答案%。

4

6 回答 6

33

其他可能来寻找答案的学习者的强制性答案。

if (number % n == 0)

在大多数情况下，您总是可以做到这一点，相信现代智能编译器。

但这并不意味着你会因为学习有趣的方式而气馁。查看这些链接。

快速整除测试（2、3、4、5、..、16）？

Bit Twiddling Hacks

于 2013-09-09T20:40:23.957 回答
26

乘法比除法花费更少的时间，所以你可以试试这个：

inline bool divisible15(unsigned int x)
{
    //286331153 = (2^32 - 1) / 15
    //4008636143 = (2^32) - 286331153
    return x * 4008636143u <= 286331153u;
}

这种方式有效，因为2^32-1（最大 32 位值）可以被 15 整除，但是如果您采用例如 7，它看起来可以工作，但并非在所有情况下都有效。

编辑：看到这个，它证明这个解决方案（在某些编译器上）比模块更快。

编辑： 这是解释和概括。

于 2013-09-09T20:36:51.157 回答
25

只需使用i % 15 == 0

  1. 由于编译器可以很容易地看到 15 永远不会更改，因此可以随意对 mod 操作进行任何优化。如果他们没有想到更好的方法来做这种优化，那么编译器编写者的工作就是你不会。

  2. 例如，很容易检查一个数字是否能被 2 整除，因为您只需检查第一位。编译器编写者知道这一点，您可以自己编写代码来检查第一点，但特别是成熟的编译器会让人们思考和研究这些事情多年。这种类型的优化非常简单，因为它只需要更改一条或两条指令，像更好的寄存器分配这样的优化更难实现

  3. 要考虑的另一件事是，您的编译器是为它所在的系统编写的，另一方面，如果您编写一些奇怪的代码可能在一个系统上同样快（可能仍然不快），那么您的代码在任何地方都是相同的) 但在另一个具有特殊硬件优化的系统上，您的代码可能会丢失一个数量级。由于您编写了一些深奥的代码来检查可分性，编译器不太可能意识到它可以优化为单个硬件操作，因此编写显而易见的事情可以让您的生活变得更好，让编译器更轻松。

  4. 由于您还没有真正检查过编写代码的速度很重要，因此奇怪的方式会使代码很难被下一个人阅读并且更容易出错（过早的优化是万恶之源）

  5. 无论输入是 16、32 还是 64 位，它仍然有效，因为它不依赖于位操作。

  6. 即使编译器编写者没有实现它，显然也有可能有人实现它（甚至你自己）

于 2013-09-09T20:47:09.763 回答
7

在一个相当现代的过程中，除以 15 不应该那么可怕。AMD 优化指南根据商（被除的值）定义它，它占用商的最高有效位的 8 + 位位置。因此，如果您的数字设置了第 63 位，那么您最终会得到 71 个周期——当然，这是一个相当长的指令。但是对于高位有几个零的 32 位数字，我们说的是 30-40 个周期。如果该数字适合 16 位值，则最大值为 23 个周期。

要获得剩余部分，还要再增加一个时钟周期。

当然，如果您一直这样做，您可能会发现这段时间很长，但我不确定是否有避免它的简单方法。

就像其他人所说的那样，编译器可能能够用更好的东西代替它。但是 15 没有，据我所知有一个明显的快速解决方案（如果你有 16 而不是 15，那么我们可以使用 的技巧x & 15）。

如果范围有限，您可以构建一个表 [vector<bool>例如，每个条目将存储 1 位]，但您很快就会遇到非缓存内存访问与除法操作一样长的问题。 ..

有一些有趣的方法可以通过对数字求和来确定一个数字是否除以 3、5 等等，但不幸的是，这些方法只能基于十进制数字，这涉及到很长的除法序列。

于 2013-09-09T21:00:06.317 回答
6

这是另一种方法，它可能比其他方法慢，但只使用加法、按位与和移位：

int divisible15(unsigned int x) {
        if (x==0) return 1;
        x = (x & 0x0f0f0f0f) + ((x&0xf0f0f0f0)>>4);
        x = (x & 0x00ff00ff) + ((x&0xff00ff00)>>8);
        x = (x & 0x0000ffff) + ((x&0xffff0000)>>16);
        x = (x & 0x0f) + ((x&0xf0)>>4);
        return x==15;
}

这个想法是，在基数 16 中被 15 整除就像在基数 10 中被 9 整除 - 数字的总和必须能被 15 整除。
所以代码总结了所有十六进制数字（类似于您计算位的方式），并且总和必须等于 15（0 除外）。

于 2013-10-08T07:45:46.277 回答
1

好吧，如果您有十六进制表示，那么在您的脑海中很容易做到。只需将所有数字相加，直到你有一个数字。如果答案是“0xf”，它可以被 15 整除。

示例0x3a98：3 + 0xa + 9 + 8 = 0x1e = 1 + 0xe = 0xf，所以它可以被 15 整除。

这适用于 X-1 上的所有因子，其中 X 是用于表示数字的基数。（对于较小的因子，最后一位数字必须能被因子整除）。

不过，不要指望这在代码中会很快。

于 2016-01-29T12:07:20.630 回答