algorithm - 如何有效地查找数字是否是 7 的倍数？

Question

有多种方法可以找出相同的结果，我尝试使用按位运算作为 -

if(((n<<3) - n)%7 == 0 ) {
    print "divide by 7";
}

还有其他更有效的方法吗？

我们可以使用以下算法判断数字是否为 3 的倍数 -

如果奇数位(在奇数位置设置的位)和偶数位之间的差值是 3 的倍数，那么数字也是。

我们也可以将上述算法推广到其他数字吗？

Answer 1

因此，如果您的数字可以用硬件支持的整数表示，并且硬件具有除法或模运算，则您应该只使用它们。它比您将要编写的任何内容都更简单，并且可能更快。甚至要与硬件竞争，您必须使用汇编程序并使用比硬件制造商做得更好的其他更快的指令，并且没有他们可以使用但您不能使用的未记录技巧的优势。

这个问题变得有趣的地方在于涉及任意大的整数。 Modulo 对此有一些技巧。例如，我可以告诉你 100000000010000010000 可以被 3 整除，尽管我的大脑与计算机相比是一个非常慢的数学处理器，因为 % 的这些属性模运算符:

• (a+b+c) % d = ( (a%d) + (b%d) + (c%d) ) %d
• (n*a) % d = ( (a%d) + (a%d) + (a%d) +... (n times) ) %d = (n*(a%d)) %d

现在请注意:

• 10% 3 = 1
• 100 % 3 = (10 * (10%3)) % 3 = 10%3 = 1
• 1000% 3 = (10 * (100%3)) %3 = 1 等等……

为了判断一个以 10 为基数的数字是否可以被 3 整除，我们只需对数字求和，看看总和是否可以被 3 整除

现在对以八进制或 base-8 表示的大二进制数使用相同的技巧(上面的@hropyatr 在评论中也指出)，并使用被 7 整除，我们有特殊情况:

8 % 7 = 1

从中我们可以推断出:

(8**N) % 7 = (8 * (8 * ( ... *( 8 * (8%7) % 7 ) % 7 ) ... %7 = 1

为了“快速”测试任意大八进制数被 7 整除的能力，我们需要做的就是将其八进制基数 8 数字相加，然后尝试将其除以 7。

最后是坏消息。

贴出的代码:

if ( (n<<3 - n) % 7 ==0 ) ...不是被 7 整除的好测试。

因为它总是产生 true对于任何 n (正如@Johnathan Leffler 所指出的)

n<<3 乘以 8，等于 8n

例如 6 不能被 7 整除，

但是6<<3 = 48和 48 - 6 = 42 ，可被 7 整除.

如果你的意思是右移 if ( (n>>3 - n ) % 7 == 0 )那也不管用。用 49 测试它， 49//8是6 , 6-49是-43虽然 49 可以被 7 整除，-43不是。

最简单的测试，if (n % 7 ) == 0在 n 溢出硬件之前，这是您的最佳选择，此时您可以找到一个例程以八进制表示 n，并对八进制数字模 7 求和。