如何判断一个二进制数能否被3整除？

Question

我想知道在二进制系统中是否有可被3整除的规则。

例如：在十进制中，如果数字的各位数字之和可被3整除，则该数字也可被3整除。例如：15 -> 1+5 = 6 -> 6 可以被3整除，所以15也可以被3整除。

重要的是要理解的是，我不是在寻找能够实现此功能的代码.. 像 bool flag = (i%3==0); 这样的代码并不是我要找的答案。我寻找的是一些易于人类理解的东西，就像十进制法则一样。

- Itay Braha

---

这个问题可能更适合在 math.SE 上提问。 - user824425

在CS.SE上的解决方案。类似的解决方案适用于任何n进制数系统和除数。 - G. Bach

检查一个数字是否可以被3整除。 - phuclv

Answer 1

请参考这个网站：如何判断二进制数是否可被三整除

基本上，从右边开始计算非零奇数位和非零偶数位的比例。如果它们的差是3的倍数，则该数字可被3整除。

例如：

15 = 1111 有2个非零奇数位和2个非零偶数位。差为0。因此15可以被3整除。

185 = 10111001 有2个非零奇数位和3个非零偶数位。差为1。因此185不能被3整除。

说明

考虑2^n值。我们知道2^0 = 1与1 mod 3同余。因此，2^1 = 2与2*1 = 2 mod 3同余。继续这个规律，我们注意到对于n为奇数的2^n，2^n与1 mod 3同余，对于偶数则与2 mod 3同余，即-1 mod 3。因此，10111001与1*1 + 0*-1 + 1*1 + 1*-1 + 1*1 + 0*-1 + 0*1 + 1*-1 mod 3同余，这与1 mod 3同余。因此，185不能被3整除。

- Benson Lin

---

非常感谢，你知道这个技巧的数学解释是什么吗？ - Itay Braha

这个技巧与测试十进制数是否能被11整除的技巧相同，关键在于“交替数字和”。当且仅当十进制下的交替数字和可被11整除时，原始数也可被整除。当你要测试的数是数字系统基数加一时，可以使用此技巧来测试其可除性。如果要测试比基数小一的数（例如十进制系统中的9），则使用普通数字和来测试。因此，也可以在十六进制表示中轻松地测试17的可除性。 - Andreas H.

十一的十进制可被整除性测试与二进制中的三相同。此外，二进制中的三是11。我有什么遗漏吗？ - Ashok Bijoy Debnath

如果你真的想深入了解，它意味着你可以将二进制数中的所有数字相加，以确定它已经被1整除（n-1可整除性规则）。 - Rogue

这里是数学证明Determine whether or not a binary number is divisible by $3$。 - phuclv

没有必要将“从右边开始”加粗，无论你从哪个方向开始计数都没关系。 - Bernard

Answer 2

我希望将比特位从右到左分成许多小块，每个块有2位，如果它们的和可被3整除，则该数字可被3整除。例如，我们有100111（39），我们将这个数字从右到左分成3个块，然后我们有11、01和10。它们的总和是110，可以被3整除，那么数字100111可以被3整除。例如2：1011010，将它们分成块，现在我们有10、10、01、01。它们的总和是110，可以被3整除，那么1011010可以被3整除。还要注意，这个技巧对于7仍然有效，但每个块必须有3位而不是2。

- greato

Answer 3

有一种方法与十进制数字的校验和非常相似：但是您需要提前划掉重复的数字（在连续两个0或两个1之后），直到您得到类似于<1|0>0101010...的形式。然后计算1的数量：如果它们的总和（=校验和）可以被3整除，则原始数字也可以被3整除。

例子：

10111001 -> 101001 ->1011 -> 10 : yields checksum 1 -> not divisible
10111010 -> 101010 : yields checksum 3 -> is divisible  
10111011 -> 101011 -> 1010 : yields checksum 2 -> not divisible

也许最容易理解这个原理的方式就是设置一个三状态的DFA（确定有限自动机）来检查是否能被三整除（例如，可以参考Chris Staekers关于计算理论的视频，第5集，形式化的DFA）。

- Rriskit