0

我试图想出一种算法来为给定的 n 位二进制数实现这一点。我尝试了许多示例，但找不到任何模式。那么我该如何进行呢？

4

5 回答 5

2

这个怎么样：

将数字转换为以 4 为基数（只需组合成对的位即可轻松实现）。4 中的 5 是 11。可以被 11 整除的以 4 为底的值有些熟悉：11、22、33、110、121、132、203、...

可被 11 整除的规则是，将所有奇数位和所有偶数位相加，然后从另一个中减去一个。如果结果可以被 11 整除（记住是 5），那么它可以被 11 整除（记住是 5）。

例如：

123456d = 1 1110 0010 0100 0000b = 132021000_4

The even digits are 1 2 2 0 0 : sum = 5d
The odd digits are   3 0 1 0  : sum = 4d

Difference is 1, which is not divisble by 5

或者另一个：

123455d = 1 1110 0010 0011 1111b = 132020333_4

The even digits are 1 2 2 3 3 : sum = 11d
The odd digits are   3 0 0 3  : sum = 6d

Difference is 5, which is a 5 or a 0

这应该有一个相当有效的硬件实现，因为它主要是位切片，然后是 N/2 加法器，其中 N 是您感兴趣的数字中的位数。

注意加减数字后，最大值为3/4 * N，所以如果你最大16位数字，你最多可以得到12个结果，所以你只需要检查0，±5和明确的±10。如果您使用 32 位数字，那么结果最多可以得到 24，因此您还需要检查结果是 ±15 还是 ±20。

于 2013-08-27T20:07:38.533 回答
2

制作一个确定性有限自动机（DFA）来实现整除性检查并在硬件中实现 DFA。

创建可被 5 整除的 DFA 很容易。您只需要注意余数并检查 2r (mod 5) 和 2r + 1(mod 5) 映射到什么。有很多网站讨论这个问题。比如这个。

还有一些众所周知的例子可以将 DFA 转换为硬件表示。

于 2013-08-27T22:40:00.667 回答
1

好吧，我刚刚想通了...数字 mod 5 = a0 * 2^0 mod 5 + a1 * 2^1 mod 5 +a2* 2^2 mod 5 + a3 * 2^3 mod 5 + a4 * 2^4 mod 5 + .... = a0 (1) + a1(2) +a2 (-1) +a3 (-2) +a4 (1) 重复 ...

因此奇数差+偶数差2倍=能被5整除

例如...考虑 110010
奇数差 = 0-0+1 = 1 或 01 偶数差 = 1-0+1 = 2 或 10

奇数差 + 偶数差的 2 倍 = 01 + 2*(10)=01 + 100 = 101 可被 5 整除。

于 2013-08-30T11:39:51.410 回答
1

每个位对被 5 整除的贡献是一个四位模式 3421。您可以一次通过任何二进制数移动 4 位，为正位添加相应的值。

例子：

100011

取 0011 应用模式 0021 sum 3

接下来的四位 0010 应用模式 0020 sum = 5

于 2014-08-20T21:16:13.603 回答
0

由于任何分配这将是一个答案肯定会在一年后过期：
在自然可被五整除的二进制表示中，位 4n 和 4n+2 的奇偶性相等，以及位 4n+1 的奇偶性相等和 4n+3。
（这完全等同于 JoshG79、notsogeek 或 james 的答案：4≡-1（mod 5）、3≡-2（mod 5）（减少了关于论证中递归的挥手，并且没有可有可无的进位处理在电路中））

于 2014-08-21T05:36:01.240 回答