编写代码来判断一个数是否能被 3 整除。函数的输入是单个位，0 或 1，如果目前收到的数字是能被 3 整除的数字的二进制表示，则输出应为 1，否则零。
例子：
input "0": (0) output 1
inputs "1,0,0": (4) output 0
inputs "1,1,0,0": (6) output 1
这是基于一个面试问题。我要求绘制逻辑门，但由于这是 stackoverflow，我将接受任何编码语言。硬件实现（verilog 等）的奖励积分。
第 a 部分（简单）：第一个输入是 MSB。
B 部分（稍微难一点）：第一个输入是 LSB。
c 部分（困难）：( a) 或 (b) 哪个更快更小？（理论上不是 Big-O 意义上的，但实际上更快/更小。）现在采用较慢/较大的，并使其与更快/较小的一样快/小。
有一个相当著名的技巧可以确定一个数字是否是 11 的倍数，方法是交替加减它的十进制数字。如果你最后得到的数字是 11 的倍数，那么你开始的数字也是 11 的倍数：
47278 4 - 7 + 2 - 7 + 8 = 0，11 的倍数 (47278 = 11 * 4298) 52214 5 - 2 + 2 - 1 + 4 = 8，不是 11 的倍数 (52214 = 11 * 4746 + 8)
我们可以将相同的技巧应用于二进制数。一个二进制数是 3 的倍数当且仅当其位的交替和也是 3 的倍数：
4 = 100 1 - 0 + 0 = 1，不是 3 的倍数 6 = 110 1 - 1 + 0 = 0，3 的倍数 78 = 1001110 1 - 0 + 0 - 1 + 1 - 1 + 0 = 0，3 的倍数 109 = 1101101 1 - 1 + 0 - 1 + 1 - 0 + 1 = 1，不是 3 的倍数
从 MSB 还是 LSB 开始都没有区别，因此以下 Python 函数在两种情况下都同样适用。它需要一个迭代器，一次返回一个位。 multiplier在 1 和 2 之间交替，而不是 1 和 -1 以避免取负数的模。
def divisibleBy3(iterator):
multiplier = 1
accumulator = 0
for bit in iterator:
accumulator = (accumulator + bit * multiplier) % 3
multiplier = 3 - multiplier
return accumulator == 0
在这里......一些新的东西......如何检查任何长度（甚至数千位）的二进制数是否可以被 3 整除。
-->((0))<---1--->()<---0--->(1) ASCII representation of graph
从图片来看。
您也可以使用它来生成可被 3 整除的数字。而且我不认为将其转换为电路会很困难。
1个使用图表的例子...
11000000000001011111111111101 可被 3 整除（再次出现在双圈中）
自己试试吧。
您还可以使用类似的技巧来执行 MOD 10，用于将二进制数转换为以 10 为基数的数字。（10 个圆圈，每个圆圈加倍圆圈，表示模数产生的值 0 到 9）
编辑：这是从左到右运行的数字，修改有限状态机以接受反向语言并不难。
注意：在图形的 ASCII 表示中，() 表示单圈，(()) 表示双圈。在有限状态机中，这些被称为状态，双圈是接受状态（表示最终可被 3 整除的状态）
呵呵
LSB 的状态表：
S I S' O
0 0 0 1
0 1 1 0
1 0 2 0
1 1 0 1
2 0 1 0
2 1 2 0
解释：0 能被三整除。0 << 1 + 0 = 0. 重复使用S = (S << 1 + I) % 3and O = 1if S == 0。
MSB 状态表：
S I S' O
0 0 0 1
0 1 2 0
1 0 1 0
1 1 0 1
2 0 2 0
2 1 1 0
解释：0 能被三整除。0 >> 1 + 0 = 0. 重复使用S = (S >> 1 + I) % 3and O = 1if S == 0。
S'与上面不同，但 O 的工作原理相同，因为S'对于相同的情况（00 和 11）为 0。由于 O 在两种情况下都相同，O_LSB = O_MSB，所以要使 MSB 与 LSB 一样短，反之亦然，只需使用两者中最短的。
这是一个简单的手动操作方法。由于 1 = 2 2 mod 3，对于每个正整数，我们得到 1 = 2 2n mod 3。此外，2 = 2 2n+1 mod 3。因此，可以通过计算奇数位位置的 1 位来确定整数是否可被 3 整除，将此数字乘以 2，将偶数位位置的 1 位的数量相加。到结果并检查结果是否能被 3 整除。
示例：57 10 =111001 2。奇数位有 2 位，偶数位有 2 位。2*2 + 2 = 6 可以被 3 整除。因此 57 可以被 3 整除。
这也是解决问题 c) 的一个想法。如果反转二进制整数的位顺序，则所有位都保持在偶数/奇数位置，或者所有位都发生变化。因此，将整数 n 的位顺序反转结果是一个整数，当且仅当 n 可被 3 整除时，该整数可被 3 整除。因此，问题 a) 的任何解决方案都适用于问题 b)，反之亦然。嗯，也许这可以帮助找出哪种方法更快......
您需要使用算术模 3 进行所有计算。这就是方法
高位：
number=0
while(!eof)
n=input()
number=(number *2 + n) mod 3
if(number == 0)
print divisible
低位：
number = 0;
multiplier = 1;
while(!eof)
n=input()
number = (number + multiplier * n) mod 3
multiplier = (multiplier * 2) mod 3
if(number == 0)
print divisible
这是一般的想法...
现在，您的职责是了解为什么这是正确的。
是的，自己做作业；）
这个想法是数字可以任意增长，这意味着你不能mod 3在这里使用，因为你的数字会增长到超出你的整数类的容量。
这个想法是注意数字发生了什么。如果你在右边添加位，你实际上在做的就是向左移动一位并添加新的位。
左移与乘以 2 相同，添加新位是添加 0 或 1。假设我们从 0 开始，我们可以根据最后一个数字的模 3 递归地执行此操作。
last | input || next | example
------------------------------------
0 | 0 || 0 | 0 * 2 + 0 = 0
0 | 1 || 1 | 0 * 2 + 1 = 1
1 | 0 || 2 | 1 * 2 + 0 = 2
1 | 1 || 0 | 1 * 2 + 1 = 0 (= 3 mod 3)
2 | 0 || 1 | 2 * 2 + 0 = 1 (= 4 mod 3)
2 | 1 || 2 | 2 * 2 + 1 = 2 (= 5 mod 3)
现在让我们看看当你向左边添加一点时会发生什么。首先，请注意：
2 2n模 3 = 1
和
2 2n+1模 3 = 2
所以现在我们必须根据当前迭代是奇数还是偶数向 mod 添加 1 或 2。
last | n is even? | input || next | example
-------------------------------------------
d/c | don't care | 0 || last | last + 0*2^n = last
0 | yes | 1 || 0 | 0 + 1*2^n = 1 (= 2^n mod 3)
0 | no | 1 || 0 | 0 + 1*2^n = 2 (= 2^n mod 3)
1 | yes | 1 || 0 | 1 + 1*2^n = 2
1 | no | 1 || 0 | 1 + 1*2^n = 0 (= 3 mod 3)
1 | yes | 1 || 0 | 2 + 1*2^n = 0
1 | no | 1 || 0 | 2 + 1*2^n = 1
实际上，LSB 方法实际上会使这更容易。在 C 中：
MSB方法：
/*
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_msb(char *input) {
unsigned value = 0;
char *p = input;
if (*p == '1') {
value &= 1;
}
p++;
while (*p) {
if (*p != ',') {
value <<= 1;
if (*p == '1') {
ret &= 1;
}
}
p++;
}
return (value % 3 == 0) ? 1 : 0;
}
LSB方法：
/*
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_lsb(char *input) {
unsigned value = 0;
unsigned mask = 1;
char *p = input;
while (*p) {
if (*p != ',') {
if (*p == '1') {
value &= mask;
}
mask <<= 1;
}
p++;
}
return (value % 3 == 0) ? 1 : 0;
}
就我个人而言，我很难相信其中一个会与另一个有很大不同。
input "0": (0) output 1
inputs "1,0,0": (4) output 0
inputs "1,1,0,0": (6) output 1
这最后的输入不应该是12，还是我误解了这个问题？
我认为 Nathan Fellman 在 a 和 b 部分上是正确的（除了 b 需要一个额外的状态：你需要跟踪你的数字位置是奇数还是偶数）。
我认为C 部分的诀窍是last在每一步都否定价值。即 0 到 0，1 到 2，2 到 1。
一个数能被 3 整除，如果它的数字之和能被 3 整除。
所以你可以添加数字并得到总和：