C++ 如何以最快的方式检查给定数字是否可以被 15 整除？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18706587/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to check if given number is divisible of 15 in fastest way?
提问by ST3
Division in processor takes much time, so I want to ask how to check in fastest way if number is divisible of some other number, in my case I need to check if number is divisible by 15.
处理器中的除法需要很多时间，所以我想问一下如何以最快的方式检查数字是否可以被其他数字整除，在我的情况下，我需要检查数字是否可以被 15 整除。
Also I've been looking through web and found funways to check if number is divisible of some number, but I'm looking for fast option.
此外，我一直在浏览网络并找到了一些有趣的方法来检查数字是否可以被某个数字整除，但我正在寻找快速选项。
NOTE:as division takes much time I'm looking for answer without /and %.
注意：由于除法需要很多时间，我正在寻找没有/和 的答案%。
回答by Max
Obligatory answer for other learners who might come looking for an answer.
其他可能来寻找答案的学习者的强制性答案。
if (number % n == 0)
if (number % n == 0)
In mostcases, you can always do this, trusting the smart modern compilers.
在大多数情况下，您总是可以做到这一点，相信智能的现代编译器。
This doesn't mean you get discouraged from learning fun ways though. Check out these links.
不过，这并不意味着您会因学习有趣的方法而气馁。查看这些链接。
回答by aaronman
Just use i % 15 == 0
只需使用 i % 15 == 0
Since the compiler can easily see that 15 will never change it can feel free to make any optimization it wants on the mod operation. It is a compiler writers job to make this kind of optimization if they haven't thought of a better way to do it you won't.
For example it is very easy to check if a number is divisible by 2 because you just check the first bit. Compiler writers know this and you could write the code yourself to check the first bit but especially a mature compiler will have people thinking about and working on these things for years. This type of optimization is a very simple one to make as it only requires changing an instruction or 2, optimizations like better register allocation are much harder to achieve
One more thing to consider is that your compiler was written for the system that it is on, you code on the other hand is the same everywhere, if you write some strange code that may be just as fast on one system (probably still not faster) but on another system which has a special hardware optimization your code may lose by an order of magnitude. Since you wrote some esoteric code to check for the divisibility the compiler is unlikely to realize it can optimize to a single hardware op, writing the obvious thing to do makes life better for you and easier for the compiler.
Since you haven't actually checked that the speed matters writing code the strange way will make the code very difficult to read for the next person and more error prone ( premature optimization is the root of all evil)
It still works whether the input is 16, 32, or 64 bits since it doesn't rely on an bit manipulation.
Even if the compiler writer hasn't implemented it, it is clearly possible for someone to implement it (even yourself)
由于编译器可以很容易地看到 15 永远不会改变，因此可以随意对 mod 操作进行任何它想要的优化。进行这种优化是编译器编写者的工作，如果他们没有想到更好的方法来做到这一点，您就不会这样做。
例如，很容易检查一个数字是否可以被 2 整除，因为您只需检查第一位。编译器作者知道这一点，您可以自己编写代码来检查第一位，但特别是成熟的编译器会让人们思考和研究这些事情多年。这种类型的优化非常简单，因为它只需要更改一条或 2 条指令，像更好的寄存器分配这样的优化很难实现
还要考虑的另一件事是，您的编译器是为它所在的系统编写的，另一方面，您的代码在任何地方都是一样的，如果您编写一些奇怪的代码，这些代码在一个系统上可能同样快（可能仍然没有更快） ) 但在另一个具有特殊硬件优化的系统上，您的代码可能会丢失一个数量级。由于您编写了一些深奥的代码来检查可分性，编译器不太可能意识到它可以优化到单个硬件操作，因此编写显而易见的事情会让您的生活更美好，编译器也更轻松。
由于您尚未实际检查编写代码的速度是否重要，这种奇怪的方式会使下一个人很难阅读代码并且更容易出错（过早优化是万恶之源）
无论输入是 16 位、32 位还是 64 位，它仍然有效，因为它不依赖于位操作。
即使编译器作者没有实现它，很明显有人可以实现它（甚至你自己）
回答by ST3
Multiplication takes less time then division, so you can try this:
乘法比除法花费的时间少，所以你可以试试这个：
inline bool divisible15(unsigned int x)
{
//286331153 = (2^32 - 1) / 15
//4008636143 = (2^32) - 286331153
return x * 4008636143u <= 286331153u;
}
This way works because 2^32-1(max 32-bit value) is divisible of 15, however if you take, for example 7, it would look like working, but wouldn't work in all cases.
这种方式有效，因为2^32-1（最大 32 位值）可以被 15 整除，但是如果你拿，例如 7，它看起来像工作，但在所有情况下都不起作用。
EDIT:See this, it proves that this solution (on some compilers) is faster then module.
编辑：看到这个，它证明这个解决方案（在某些编译器上）比模块更快。
EDIT:Hereis the explanation and the generalization.
编辑：这是解释和概括。
回答by Mats Petersson
On a reasonably modern process, dividing by 15 shouldn't be that terrible. The AMD optimisation guide defines it based on the quotient (the value that is being divided), and it takes 8 + bit position of the most significant bit of the quotient. So if your numbers have the 63rd bit set, you end up with 71 cycles - which is quite a long instruction, of course. But for a 32-bit number with a few zeros in the top bits, we're talking 30-40 cycles. If the number fits in a 16-bit value, we the maximum is 23 cycles.
在一个相当现代的过程中，除以 15 不应该那么糟糕。AMD优化指南是根据商（被除的值）定义的，取商最高位的8+位位置。因此，如果您的数字设置了第 63 位，那么您最终会得到 71 个周期——当然，这是一条相当长的指令。但是对于高位有几个零的 32 位数字，我们说的是 30-40 个周期。如果该数字适合 16 位值，则最大值为 23 个周期。
To get the remainder is one more clockcycle on top of that.
获得余数是在此基础上再增加一个时钟周期。
If you are doing this ALL the time, of course, you may find that this time is quite long, but I'm not sure there is a trivial way to avoid it.
如果您一直都这样做，当然，您可能会发现这个时间很长，但我不确定是否有一种简单的方法可以避免它。
Like others have said, compiler may be able to replace it with something better. But 15 does not, to my knowledge have an obvious fast solution (if you have 16 instead of 15, then we can use the trick of x & 15).
就像其他人所说的那样，编译器可能会用更好的东西替换它。但是 15 没有，据我所知有一个明显的快速解决方案（如果你有 16 而不是 15，那么我们可以使用 的技巧x & 15）。
If it's a limited range, you could build a table [vector<bool>for example, which will store 1 bit per entry], but you'll quite soon run into the problem that the non-cached memory access takes just as long as a divide operation...
如果范围有限，您可以构建一个表 [vector<bool>例如，每个条目将存储 1 位]，但您很快就会遇到非缓存内存访问所需的时间与除法操作一样长的问题。 ..
There are some interesting ways to figure out if a number divides by 3, 5 and so on by summing the digits, but unfortunately, those only work based on decimal digits, which involves a long sequence of divides.
有一些有趣的方法可以通过对数字求和来确定一个数字是否被 3、5 等除，但不幸的是，这些方法只能基于十进制数字，这涉及很长的除法序列。
回答by ugoren
Here's another approach, which is probably slower than others, but uses only addition, bitwise-and and shift:
这是另一种方法，它可能比其他方法慢，但仅使用加法、按位与和移位：
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;
}
The idea is that divisibility by 15, in base 16, is like divisibility by 9 in base 10 - the sum of digits must be divisible by 15.
So the code sums up all hex digits (similarly to the way you count bits), and the sum must equal 15 (except for 0).
这个想法是，在基数 16 中被 15 整除就像在基数 10 中被 9 整除 - 数字的总和必须被 15 整除。
所以代码总结了所有的十六进制数字（类似于你计算位的方式），并且总和必须等于 15（0 除外）。
回答by Roddy
Well, it's very easy to do in your head if you have the hex representation. Just sum all the digits, until you have a single digit. If the answer is '0xf', it's divisible by 15.
好吧，如果你有十六进制表示，这很容易在你的脑海中完成。只需将所有数字相加，直到你有一个数字。如果答案是“0xf”，则它可以被 15 整除。
Example 0x3a98: 3 + 0xa + 9 + 8 = 0x1e = 1 + 0xe = 0xf, so that's divisible by 15.
示例0x3a98：3 + 0xa + 9 + 8 = 0x1e = 1 + 0xe = 0xf，所以它可以被 15 整除。
This works for all factors on X-1, where X is the base used to represent the number. (For smaller factors, the final digit must be divisible by the factor).
这适用于 X-1 上的所有因子，其中 X 是用于表示数字的基数。（对于较小的因子，最后一位数字必须能被因子整除）。
Don't expect this to be fast in code, though.
不过，不要指望这在代码中会很快。
