编写代码确定一个数是否能被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），则会给予额外的奖励。
第一部分（易）：第一个输入是最高有效位（MSB）。
第二部分（较难）：第一个输入是最低有效位（LSB）。
第三部分（困难）：哪个更快、更小，（a）还是（b）？（不是从大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的倍数
从最高位开始或者最低位开始都没有影响，所以下面这个 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整除的数字。我想将其转换为电路也不难。
以下是使用图形的一个示例...
11000000000001011111111111101可以被3整除（最后又回到双倍圆圈）
试试吧。
您还可以使用类似的技巧执行MOD 10，用于将二进制数转换为十进制数。（10个圆圈，每个圆圈都有两倍圆圈，表示模数为0到9的值）
编辑：这是针对从左到右的数字运行的，但是修改有限状态机接受反向语言并不困难。
注意：在图形的ASCII表示中，()表示单个圆圈，(())表示双倍圆圈。在有限状态机中，它们被称为状态，而双倍圆圈是接受状态（表示最终可被3整除的状态）。
嗯
最低有效位的状态表：
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可以被3整除。 0 << 1 + 0 = 0。 如果S == 0，则重复使用S = (S << 1 + I) % 3和O = 1。
最高位状态表：
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是3的倍数。0 >> 1 + 0 = 0。重复使用S = (S >> 1 + I) % 3和O = 1，如果S == 0。
S'与上述不同，但O的工作方式相同，因为在相同情况下（00和11），S'也等于0。由于O在两种情况下是相同的，所以O_LSB = O_MSB，因此要使MSB和LSB中较短的一个尽可能短，或者反之，只需使用两者中最短的一个即可。
number=0
while(!eof)
n=input()
number=(number *2 + n) mod 3
if(number == 0)
print divisible
LSB:
number = 0;
multiplier = 1;
while(!eof)
n=input()
number = (number + multiplier * n) mod 3
multiplier = (multiplier * 2) mod 3
if(number == 0)
print divisible
这是一个通用的想法...
现在，你需要明白为什么这是正确的。
当然，要自己完成作业；)
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)
现在让我们看看向左添加一点会发生什么。首先请注意：
22n mod 3 = 1
和
22n+1 mod 3 = 2
因此，根据当前迭代次数是奇数还是偶数，我们必须将模数加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
input "0": (0) output 1
inputs "1,0,0": (4) output 0
inputs "1,1,0,0": (6) output 1
这个最后一次输入应该是12，还是我误解了问题？
实际上，最低有效位方法会使这更容易。在 C 中：
最高有效位方法：
/*
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;
}
就我个人而言，我很难相信其中一个会与另一个有显著的不同。
如果一个数字的各个位数之和可以被3整除，那么这个数字也能被3整除。
因此，你可以将各个位数相加并得到总和：
我认为Nathan Fellman在A和B部分是正确的（除了B部分需要一个额外的状态：您需要跟踪您的数字位置是奇数还是偶数）。
我认为C部分的诀窍是在每个步骤中否定last值。即，0变成0，1变成2，2变成1。