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

Question

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

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

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

我们可以使用以下算法找到数字是否是 3 的倍数 -

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

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

Answer 1

我认为 if(n%7 == 0) 是检查被 7 整除的更有效方法。
但是，如果您正在处理大量数据并且不能直接执行 modulus 操作，那么这可能会有所帮助：

当且仅当 x − 2y 可以被 7 整除时，10x + y 形式的数字才能被 7 整除。换句话说，从剩余数字组成的数字中减去最后一位数字的两倍。继续这样做，直到得到一个已知可以被 7 整除的数字。当且仅当使用此过程获得的数字可以被 7 整除时，原始数字才能被 7 整除。
例如，数字 371: 37 − (2×1) = 37 − 2 = 35; 3 − (2 × 5) = 3 − 10 = −7; 因此，由于 −7 可以被 7 整除，因此 371 可以被 7 整除。
另一种方法是乘以3。 10x + y 形式的数除以 7 后的余数与 3x + y 相同。必须将原始数字的最左边的数字乘以 3，加上下一位，除以 7 取余，然后从头继续：乘以 3，加上下一个数字等
例如，数371: 3×3 + 7 = 16余数2，以及2×3 + 1 = 7.
这个方法可以用来求除以7的余数
P.S: reference

Answer 2

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

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

现在请注意：

为了判断一个以 10 为基数的数字是否可以被 3 整除，我们只需将数字相加并查看总和是否可以被 3 整除

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

8 % 7 = 1

从中我们可以推断出：

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

以便"quickly"测试一个任意大的八进制数被 7 整除的能力，我们需要做的就是将其八进制基数 8 的数字相加，然后尝试将其除以 7。

最后，坏消息。

贴出的代码：

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

因为它总是对任何 n 产生 true（正如@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 取模求和。

How to find if the number is a multiple of 7 efficiently?