不使用%和/运算符的5的可分性

Question

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

Answer 1

一个好的起点是研究如何通过乘法和位移完成除法. 这个问题是一个值得关注的地方.

特别是,您可以按照附加的帖子来实现以下策略.首先,使用乘法和位移"除以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
}

Answer 2

我想看到这样一个算法有两个原因:(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; 如果为零,则为五的倍数.