检查数字是否可被3整除 [英] Check if a number is divisible by 3

问题描述

编写代码以确定一个数字是否可以被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整除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！