Check if a number is divisible by 3
division, modulo, puzzle
Solution
Heh
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.
Problem
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 stackoverflow 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.