使用按位运算验证可除性规则

Question

如何使用按位运算验证数字n是否可整除x？

我在这方面找到了很多相关链接，但我不清楚它们，因为它们不在 Python 中。例如，如果我想验证是否81可以被3,9或整除4怎么办？

我想使用按位运算，我想了解如何使用 Python 实现这一点。

Answer 1

顾名思义，按位运算让猜测对数字的二进制表示进行运算。这意味着它们将非常有效地测试被幂或 2 的整除性，但几乎无法用于任何其他情况。

例子：

• n 可被 2 整除： n & 1 == 0
• n 可被 4 整除： n & 3 == 0
• n 可被 8 整除： n & 7 == 0

还有其他可以使用的整除规则：您可以调整淘汰 9 或 11以测试 15 或 17 的可整除性（基数 16 用于半字节每个字节），但作为单个整数除法通常比进行许多更简单的操作更快（累加器直接处理 32 位或 64 位的数字）它们很少使用......

如果您的要求是测试 3 和 9 的可整性，您可以将9调整为 3 = 4 - 1，将11 调整为 9 =8+1。81 = 0b1010001

• 3：2 位数字的总和必须能被 3 整除 - 从很小的权重开始：01+00+01+01=0b11 (=3)：可整除
• 9：奇3位数字之和减去偶数之和必须被9=0b1001整除 - 奇数：001+001=010，偶数：010 - 差为0：可整除

您可以使用移位 ( >>) 和二进制轻松编写代码&