不使用％和/运算符的5的可分性
如何在不使用％和/运算符的情况下检查数字是否可被5整除。 我想要一个最快的算法来解决这个问题。
一个好的起点是研究如何通过乘法和位移完成除法。 这个问题是一个值得关注的地方。
特别是，您可以按照附加的post来实现以下策略。 首先，使用乘法和位移“除以5”：
int32_t div5(int32_t dividend) { int64_t invDivisor = 0x33333333; return 1 + (int32_t) ((invDivisor * dividend) >> 32); }
然后，取结果并乘以5：
int result = div5(dividend) * 5;
然后， result == dividend ，只有dividend可以被5整除。
if(result == dividend) { // dividend is divisible by 5 } else { // dividend is not divisible by 5 }
我想看到这样一个算法有两个原因：（1）作业，或者（2）为没有有效分割指令的微控制器编写有效代码。 假设你的理由是第二个，但允许它可能是第一个，我不会给你一个完整的解决方案，但会建议如果你把你的数字分成每个四位的数字块，只有当原始数字为时，所有这些块的总和才能被5整除; 请注意，执行此类计算时，您必须避免溢出，或者在结果中添加已发生的溢出次数。 我不知道在C中使用后者的任何有效方法，但在许多机器语言中它很容易。 举个简单的例子，在8051上如果有一个32位整数，就可以这样：
mov a,Number ; Byte 0 add a,Number+1 ; Byte 1 adc a,Number+2 ; Byte 2, plus carry from last add adc a,Number+3 ; Byte 3, plus carry from last add adc a,#0 ; Add in carry, if any (might overflow) adc a,#0 ; Add in carry, if any (can't overflow)
请注意，在机器代码中，将运算符添加到数字中比执行16位数学运算要快得多。
一旦该值减小到0-255的范围，就可以将高4位添加到低4位以获得0到30范围内的值。可以测试7个这样的值是5的倍数，或努力进一步减少可能值的数量[例如，如果该值至少为15，则减去15; 如果至少10，减去10; 如果5，减去5; 如果为零，则为五的倍数。
让我们用基数2表示数字。我们有：
abcdefgh*101 = ABCDEFGHIJ
要么
+abcdefgh00 + abcdefgh ---------- ABCDEFGHIJ
我们获得了ABCDEFGHIJ并希望找到abcdefgh 。
如果你交替 – 和+ ABCDEFGH及其连续的右移2，你会得到……
+ ABCDEFGH - ABCDEF + ABCD - AB ----------- + abcdefgh + abcdef - abcdef - abcd + abcd + ab - ab ----------- abcdefgh
答案！
它终于解锁了，所以我可以解释我的评论，顺便说一句，它产生的代码比GCC对x % 5 == 0更好。 看到这里 ，填写
#include bool divisible_by_5(uint32_t x) { return x % 5 == 0; } bool divisible_by_5_fast(uint32_t x) { return x * 0xCCCCCCCD <= 0x33333333; }
我假设无符号输入，因为OP提出了一种只适用于正输入的算法。 这种方法可以扩展到带符号的输入，但它有点乱。
0xCCCCCCCD是5的模乘乘数 ，模2 32 。 将（ n * k ）的倍数（例如， n * k ）乘以（模乘）乘法逆相当于除以k，因为
(n * k) * inv(k) = // use associativity n * (k * inv(k)) = // use definition of multiplicative inverse n * 1 = // multiplicative identity n
模数幂为2，如果是奇数，则数字具有模乘法逆。
由于乘以奇数是可逆的并且实际上是双射，因此它不能将k的任何非倍数映射到0 - （2 32 -1）/ k范围。
因此，当它超出该范围时，它不能是k的倍数。
0x33333333是（2 32 -1）/ 5，所以如果x * 0xCCCCCCCD更高， x不能是5的倍数。
如果总和可以被5整除，则添加所有字节并检查（通过表查找）。
保持减去5的倍数，如50,500,100等。从大数字开始。 如果结果为负数，则用较小的数字减去，直到达到0.否则数字不可分。
bool trythis(int number){ Int start = number; Do{ start = start - 5; } while (start > 5) If (start == 5 || start == 0) { Return true; } else return false; }
在十进制中，如果数字的总和可以被3或9整除，则数字可以被3或9整除
这同样适用于基数b中b - 1任何除数。 例如，我们可以将基数16中的数字相加，并取模3或5来得到模3或5的数。事实上，我们可以在任何基数2 4k中检查除数5，如16,256,4096 …
使用该属性我们有以下解决方案
unsigned mod5(unsigned x) { unsigned mod = 0; while (x) { mod += x & 0x0F; x >>= 4; } while (mod >= 15) { if (mod == 15) return 0; mod = (mod >> 4) + (mod & 0x0F); } return mod; }
或者可以像这样进一步优化
unsigned isDivisibleBy5(unsigned x) { x = (x >> 16) + (x & 0xffff); x = (x >> 8) + (x & 0x00ff); x = (x >> 4) + (x & 0x000f); return !!((0x1084210842108421ULL >> x) & 1); }
Typecast或转换为字符串，然后查看最终字符是5还是0。