问题描述
编写代码以确定一个数字是否可以被3整除.该函数的输入是一个单位，即0或1，如果到目前为止接收到的数字是1，则输出应为1.数字的二进制表示形式，该数字可以被3整除，否则为零.
Write code to determine if a number is divisible by 3. The input to the function is a single bit, 0 or 1, and the output should be 1 if the number received so far is the binary representation of a number divisible by 3, otherwise zero.
示例:
input "0": (0) output 1
inputs "1,0,0": (4) output 0
inputs "1,1,0,0": (6) output 1
这是基于采访问题.我要求绘制逻辑门，但是由于这是stackoverflow，因此我将接受任何编码语言.硬件实现的奖励点(verilog等).
This is based on an interview question. I ask for a drawing of logic gates but since this is stackoverflow I'll accept any coding language. Bonus points for a hardware implementation (verilog etc).
a部分(简单):首先输入的是MSB.
Part a (easy): First input is the MSB.
b部分(稍微难一点):第一个输入是LSB.
Part b (a little harder): First input is the LSB.
c部分(困难) :( a)或(b)哪个更快，更小? (从理论上讲不是Big-O，而是实际上更快/更小.)现在选择较慢/更大的一个，使其与更快/更小一样快/小.
Part c (difficult): Which one is faster and smaller, (a) or (b)? (Not theoretically in the Big-O sense, but practically faster/smaller.) Now take the slower/bigger one and make it as fast/small as the faster/smaller one.
推荐答案
嘿
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被3整除. 0 << 1 + 0 = 0.如果S == 0，请重复使用S = (S << 1 + I) % 3和O = 1.
Explanation: 0 is divisible by three. 0 << 1 + 0 = 0. Repeat using S = (S << 1 + I) % 3 and O = 1 if 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被3整除. 0 >> 1 + 0 = 0.如果S == 0，请重复使用S = (S >> 1 + I) % 3和O = 1.
Explanation: 0 is divisible by three. 0 >> 1 + 0 = 0. Repeat using S = (S >> 1 + I) % 3 and O = 1 if S == 0.
S'与上面的有所不同，但是O的工作原理相同，因为对于相同的情况(00和11)，S'为0.由于两种情况下的O相同，所以O_LSB = O_MSB，因此要使MSB与LSB一样短，反之亦然，请使用两者中最短的一个.
S' is different from above, but O works the same, since S' is 0 for the same cases (00 and 11). Since O is the same in both cases, O_LSB = O_MSB, so to make MSB as short as LSB, or vice-versa, just use the shortest of both.
这篇关于检查数字是否可被3整除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！