如何检查给定的数字是否能以最快的方式整除15？

Question

处理器中的分区需要很长时间,所以我想问如何以最快的方式检查数字是否可以被其他数字整除,在我的情况下我需要检查数字是否可被15整除.

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

注意:由于分工需要很长时间,我正在寻找没有/和的答案%.

Answer 1

对于可能会寻找答案的其他学习者的强制性答案.

if (number % n == 0)

在大多数情况下,您始终可以这样做,相信智能的现代编译器.

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

快速可分性测试(2,3,4,5,...,16)？

比特扭曲黑客

Answer 2

乘法比划分花费更少的时间,所以你可以试试这个:

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,它看起来像工作,但不会在所有情况下都有效.

编辑:看到这一点,它证明了这个解决方案(在某些编译器上)比模块更快.

编辑: 这是解释和概括.

Answer 3

只是用 i % 15 == 0

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

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

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

4. 由于你还没有真正检查速度是否与编写代码有关,奇怪的方式会使代码很难为下一个人阅读而且更容易出错(过早的优化是所有邪恶的根源)

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

6. 即使编译器编写器没有实现它,显然有人可以实现它(甚至你自己)

Answer 4

在一个相当现代的过程中,除以15不应该那么可怕.AMD优化指南根据商(被分割的值)定义它,并且它需要商的最高有效位的8 +位位置.因此,如果你的数字设置了第63位,你最终会得到71个周期 - 当然这是一个很长的指令.但对于32位数字,顶部位有几个零,我们说的是30-40个周期.如果数字符合16位值,则最大值为23个周期.

为了得到余数,还有一个时钟周期.

当然,如果你一直这样做,你可能会发现这个时间很长,但我不确定是否有一种琐碎的方法可以避免它.

像其他人所说,编译器可能能够用更好的东西取而代之.但是15并没有,据我所知有一个明显的快速解决方案(如果你有16而不是15,那么我们可以使用诀窍x & 15).

如果它是一个有限的范围,你可以构建一个表[ vector<bool>例如,每个条目将存储1位],但你很快就会遇到非缓存内存访问只需要除法运算的问题. ..

有一些有趣的方法可以通过对数字进行求和来确定一个数字是否除以3,5等等,但不幸的是,这些仅基于十进制数字工作,这涉及一长串的除法.

Answer 5

这是另一种方法,可能比其他方法慢,但只使用加法,按位和移位:

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).