能被 5 整除的二进制数的正则表达式

Question

我想为能被 5 整除的二进制数编写一个正则表达式。
我已经完成了可被 2 整除的二进制数和 3 的正则表达式，但我找不到 5 的正则表达式。

有什么建议吗？

Answer 1

(0|1(10)*(0|11)(01*01|01*00(10)*(0|11))*1)*

添加

^$

以使用正则表达式进行测试。 在这里查看它的工作情况。

---

您可以构建一个 DFA 并将其转换为正则表达式。 DFA 已经内置于另一个答案中。你可以读一下，它解释得很好。

---

总体思路是删除节点，添加边。

变成：

---

使用此转换和我链接的答案中的 DFA，以下是获取正则表达式的步骤：
（编辑：请注意，图中的标签“Q3”和“Q4”已被错误地交换。这些状态表示模数 5 后的余数。）

Answer 2

2^0 =  1 =  1 mod 5
2^1 =  2 =  2 mod 5
2^2 =  4 = -1 mod 5
2^3 =  8 = -2 mod 5
2^4 = 16 =  1 mod 5
2^5 = 32 =  2 mod 5
   ...     -1 mod 5
   ...     -2 mod 5

所以我们有一个 1, 2, -1, -2 模式。有两种仅数字符号交替的子模式：令 n 为数字，最低有效数字为 0；奇怪的图案是

(-1)^(n)

甚至图案是

2x((-1)^(n))

那么，如何使用这个？

设原数为100011，将数字分成偶数和奇数两部分。分别对每个部分的数字求和。将奇数位之和乘以2。如果结果能被偶数位之和整除，则原数能被5整除，否则不可整除。示例：

100011
1_0_1_ 1+0+1 = 2
_0_0_1 0+0+1 = 1; 1x2 = 2

2 mod(2) equals 0? Yes. Therefore, original number is divisible.

如何在正则表达式中应用它？在正则表达式中使用 callout 函数就可以应用它。标注提供了一种在正则表达式模式匹配过程中临时将控制传递给脚本的方法。

但是ndn的答案更合适也更容易，所以我推荐使用他的答案。