4

如何在不使用 % 和 / 运算符的情况下检查数字是否可被 5 整除。 我想要一个最快的算法来解决这个问题。

4

9 回答 9

11

一个好的起点是研究如何通过乘法和位移来完成除法。 这个问题值得一看。

特别是，您可以按照附加的帖子来了解以下策略。首先，使用乘法和位移“除以 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
}
于 2013-06-14T17:11:26.203 回答
6

我可以看到需要这种算法的两个原因：（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 范围内的值。可以测试七个这样的值，它们是 5 的倍数，或努力进一步减少可能值的数量[例如，如果该值至少为 15，则减去 15；如果至少 10，则减 10；如果是 5，则减 5；如果为零，则为五的倍数]。

于 2013-06-14T17:22:06.687 回答
3

让我们表示以 2 为底的数字。我们有：

abcdefgh*101 = ABCDEFGHIJ

或者

+abcdefgh00
+  abcdefgh
 ----------
 ABCDEFGHIJ

我们被给予ABCDEFGHIJ并且想要找到abcdefgh。

如果你交替 - 和 +ABCDEFGH连续右移 2，你会得到......

+  ABCDEFGH
-    ABCDEF
+      ABCD
-        AB
-----------
+  abcdefgh
+    abcdef
-    abcdef
-      abcd
+      abcd
+        ab
-        ab
-----------
   abcdefgh

答案！

于 2013-06-14T17:44:27.937 回答
1

它终于解锁了，所以我可以解释我的评论，顺便说一下，它生成的代码比 GCC 为x % 5 == 0. 看这里，填写

#include <stdint.h>
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。将 k 的倍数（例如n * k）乘以（模）乘法逆元相当于除以 k，因为

(n * k) * inv(k) =
// use associativity
n * (k * inv(k)) =
// use definition of multiplicative inverse
n * 1 =
// multiplicative identity
n

模二的幂，一个数有一个模乘逆当且仅当它是奇数。

由于乘以奇数是可逆的并且实际上是双射，因此它不能将任何非倍数 k 映射到 0 - (2 32 -1)/k 范围。

因此，当它超出该范围时，它不可能是 k 的倍数。

0x33333333是 (2 32 -1)/5，所以如果x * 0xCCCCCCCD更高，x则不可能是 5 的倍数。

于 2013-06-15T08:40:58.550 回答
0

添加所有字节并检查（通过查表）总和是否可被 5 整除。

于 2013-06-14T17:02:29.080 回答
0

继续减去 5 的倍数，例如 50、500,100 等。从大数开始。如果结果为负数，则用较小的数字减去，直到达到 0。否则该数字不可整除。

于 2013-06-14T17:06:27.420 回答
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;
}
于 2013-06-14T17:19:07.893 回答
0

在十进制中，如果数字之和可以被 3 或 9 整除，则一个数字可以被 3 或 9 整除

这同样适用于以b 为底的任何除数b - 1。例如，我们可以对以 16 为底的数字求和，然后取模 3、5 或 15 以得到模 3、5 或 15 的数字。请参阅如何在不使用任何算术运算的情况下找到 x mod 15？

事实上，我们可以在任何基数 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);
}
于 2018-08-07T12:25:32.447 回答
-3

类型转换或转换为字符串，然后查看最后一个字符是 5 还是 0。

于 2013-06-14T17:02:00.217 回答