位程序设计

Question

对于不同的数字，我们是否有任何一般的方法或特定的方法，通过这些方法我们可以知道一个给定的数字n在它的二进制表示中可以被另一个数字m整除。

例如：

n=23 (00010111)
m=3

如果设置在偶数和奇点位置的位数之间的差值可被3整除，则该数字可被3整除。

• 位设置为1在偶数位置=1
• 在奇数位置设置为1的位=3

因此，3 - 1 = 2不能被3整除，因此23不能被3整除。

我想问一问，是否还有其他方法可以找出一个数字是否可以被2，4，5，6，7等除以？

Answer 1

你不能为他们找到一个简单的规则。以下是如何创建这样的规则的想法。

让我们先来谈谈基数10，想象一下abcdefg这个数字。这个数字实际上是：

g + 10*f + 10^2*e + 10^3*d + 10^4*c + 10^5*b + 10^6*a

如我们所知，(a+b)%c等于(a%c+b%c)%c，(a*b)%c等于((a%c)*(b%c))%c(您可以更好地了解了解同余的这些属性)

因此，让我们通过以下方法来查看我们的剩余数字：

• 2 (g + 10*f + 10^2*e + 10^3*d + 10^4*c + 10^5*b + 10^6*a)%2 = (g%2 +0+0+0+0+0+0+0+0+ 0)%2 = g%2 因此，如果最后一个数字可被2整除，则该数字可被2整除。
• 3. (g + 10*f + 10^2*e + 10^3*d + 10^4*c + 10^5*b + 10^6*a)%3 = (g%3 + f%3 + e%3 + d%3 + c%3 + b%3 + a%3)%3 =.对此数字重复操作 因此，一个数字可以被3整除，它的数字之和可以被3整除。
• 4. (g + 10*f + 10^2*e + 10^3*d + 10^4*c + 10^5*b + 10^6*a)%4 = (g%4 + 2*f%4 +0+0+0+0+ 0)%4 =.如果大于4，重复 因此，一个数字可以被4整除，如果它的最后一个数字加上最后一个数字之前的数字的两倍，则它可以被4整除。
• 5 (g + 10*f + 10^2*e + 10^3*d + 10^4*c + 10^5*b + 10^6*a)%5 = (g%5 +0+0+0+0+0+0+0+0+ 0)%5 = g%5 因此，如果一个数字的最后一个数字是0或5，则它可以被5整除。
• ..。
• 11 (g + 10*f + 10^2*e + 10^3*d + 10^4*c + 10^5*b + 10^6*a)%11 = (g %11-f%11+e%11-d%11+c%11-b%11+ a%11)%11 =(g-f+e-d+c-b+c-b+ a)%11 =.对此数字重复操作 (请注意，10%11可视为-1 (它们是一致的))
• 诸若此类!

正如你所看到的，在基数10中，11的余数给出了和基数2中的3的余数相同的公式，这不是巧合。

现在让我们假设我们的数字在基数2中。因此，abcdefg的计算结果为：

g + 2*f + 2^2*e + 2^3*d + 2^4*c + 2^5*b + 2^6*a

求公式的方法与上述方法完全相同。这里唯一简单的地方是，如果除数大于1，那么除数的所有数字的剩余部分就是数字本身(因为数字只有0或1)，所以所有的digit%divisor都变成了digit。这根本改变不了方法学。

让我们看看剩下的数字

• 2 (g + 2*f + 2^2*e + 2^3*d + 2^4*c + 2^5*b + 2^6*a)%2 = (g +0+0+0+0+0+0+0+ 0)%2 =g 因此，如果一个数字的最后一个数字是0，则它可以被2整除。
• 3. (g + 2*f + 2^2*e + 2^3*d + 2^4*c + 2^5*b + 2^6*a)%3 = (g -f+e-d+c-b+ a)%3 =.对此数字重复操作
• 4. (g + 2*f + 2^2*e + 2^3*d + 2^4*c + 2^5*b + 2^6*a)%4 = (g + 2*f +0+0+0+0+0+0+ 0)%4 = 因此，一个数字可以被4整除，如果它的最后一个数字加上最后一个数字之前的数字的两倍，则它可以被4整除。
• 5 (g + 2*f + 2^2*e + 2^3*d + 2^4*c + 2^5*b + 2^6*a)%5 = (g + 2*f -e- 2*d +c+ 2*b - a)%5 =.对此数字重复操作
• 诸若此类

Answer 2

由于找不到一个数字是否可以被另一个数字整除的一般方法(例如，请参阅这里 )，因此显然无法在二进制表示中找到它。