c - 位编程

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(了解 congruence 可以更好地了解这些属性)

那么，让我们通过以下方式查看数字的剩余部分:

• 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
  

  因此，如果一个数的最后一位是 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 + 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%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)%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 =
  ... 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
  

• 等等