逻辑设计中判断一个数是否能被3整除
Check if a number is divisible by 3 in logic design
我在网站上看到 post，但我不明白答案，请问我能得到解释吗：
问题：
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.
Examples:
input "0": (0) output 1
inputs "1,0,0": (4) output 0
inputs "1,1,0,0": (6) output 1
This is based on an interview question. I ask for a drawing of logic gates but since this is Whosebug I'll accept any coding language. Bonus points for a hardware implementation (verilog etc).
Part a (easy): First input is the MSB.
Part b (a little harder): First input is the LSB.
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.
答案：
State table for 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
Explanation: 0 is divisible by three. 0 << 1 + 0 = 0. Repeat using S = (S << 1 + I) % 3 and O = 1 if S == 0.
State table for 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
Explanation: 0 is divisible by three. 0 >> 1 + 0 = 0. Repeat using S = (S >> 1 + I) % 3 and O = 1 if S == 0.
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.
感谢您提前回答。
嗯，我想这个问题并不完全是题外话，因为你问的是逻辑设计，但你必须自己编写代码。
您在 S 列中有 3 个状态。 这些跟踪当前完整输入的值mod 3。因此，S0 表示当前输入 mod 3 为 0，因此可以被 0 整除（还要记住 0 可以被 3 整除）。 S1表示余数为1，S2表示余数为2.
I列给出当前输入（0或1），S'给出下一个状态（换句话说，新数字mod3）。
对于'LSB'，新数是旧数<< 1，加上0或1。写出table。对于初学者来说，如果旧的 modulo 是 0，那么如果输入位是 0，新的 modulo 将是 0，如果新输入是 1，那么新的 modulo 将是 1。这给了你第一个第 2 行 table。剩下的填写留给你作为练习。
请注意，如果下一个状态为 0，则 O 列仅为 1，正如预期的那样。
我在网站上看到 post，但我不明白答案，请问我能得到解释吗：
问题：
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.
Examples:
input "0": (0) output 1 inputs "1,0,0": (4) output 0 inputs "1,1,0,0": (6) output 1This is based on an interview question. I ask for a drawing of logic gates but since this is Whosebug I'll accept any coding language. Bonus points for a hardware implementation (verilog etc).
Part a (easy): First input is the MSB. Part b (a little harder): First input is the LSB. 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.
答案：
State table for 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 0Explanation: 0 is divisible by three. 0 << 1 + 0 = 0. Repeat using S = (S << 1 + I) % 3 and O = 1 if S == 0.
State table for 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 0Explanation: 0 is divisible by three. 0 >> 1 + 0 = 0. Repeat using S = (S >> 1 + I) % 3 and O = 1 if S == 0.
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.
感谢您提前回答。
嗯，我想这个问题并不完全是题外话，因为你问的是逻辑设计，但你必须自己编写代码。
您在 S 列中有 3 个状态。 这些跟踪当前完整输入的值mod 3。因此，S0 表示当前输入 mod 3 为 0，因此可以被 0 整除（还要记住 0 可以被 3 整除）。 S1表示余数为1，S2表示余数为2.
I列给出当前输入（0或1），S'给出下一个状态（换句话说，新数字mod3）。
对于'LSB'，新数是旧数<< 1，加上0或1。写出table。对于初学者来说，如果旧的 modulo 是 0，那么如果输入位是 0，新的 modulo 将是 0，如果新输入是 1，那么新的 modulo 将是 1。这给了你第一个第 2 行 table。剩下的填写留给你作为练习。
请注意，如果下一个状态为 0，则 O 列仅为 1，正如预期的那样。