硬件算法以确定数字是否可以被五整除

Question

我正在尝试为给定的 n 位二进制数想出一种算法来实现它。我尝试了很多例子，但无法找出任何模式。那我该怎么办呢？

Answer 1

这个怎么样:

将数字转换为基数 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位的数max，结果最多可以得到12，所以只需要检查0 , ±5 和 ±10 明确。如果您使用的是 32 位数字，那么您最多可以获得 24 个结果，因此您还需要检查结果是 ±15 还是 ±20。