3

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

例如：

n=23 (00010111)
m=3

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

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

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

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

4

2 回答 2

5

您无法为所有这些都找到一个简单的规则。以下是如何创建此类规则的想法。

让我们先谈谈以 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)%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 =
... repeat operation for this number

    因此，一个数可以被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 =
... repeat if bigger than 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)%5 =
g%5

    因此，一个数可以被 5 整除，如果它的最后一位是 0 或 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 + a)%11 =
... repeat operation for this number

    （注意 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%divisors 都变成了简单的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)%2 =
g

    因此，一个数可以被 2 整除，如果它的最后一位是 0

  • 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 =
... repeat operation for this number

  • 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)%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 =
... repeat operation for this number

  • 等等

于 2012-05-30T19:00:50.613 回答
0

由于没有一般方法可以确定一个数字是否可以被另一个数字整除（例如，请参见此处），因此显然无法以二进制表示形式找出它。

于 2012-05-30T18:43:08.160 回答