位编程

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)%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整除

• 五

  (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%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
  

  因此,如果最后一个数字为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整除

• 五

  (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
  

• 等等