Check if a number is divisible by 3 in logic design

Question

i seen a post on the site about it and i didn't understand the answer, can i get explanation please:

question:

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.

answer:

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.

thanks for the answers in advanced.

Answer 1

Well, I suppose the question isn't entirely off-topic, since you asked about logic design, but you'll have to do the coding yourself.

You have 3 states in the S column. These track the value of the current full input mod 3. So, S0 means the current input mod 3 is 0, and so is divisible by 0 (remember also that 0 is divisible by 3). S1 means the remainder is 1, S2 means that the remainder is 2.

The I column gives the current input (0 or 1), and S' gives the next state (in other words, the new number mod 3).

For 'LSB', the new number is the old number << 1, plus either 0 or 1. Write out the table. For starters, if the old modulo was 0, then the new modulo will be 0 if the input bit was 0, and will be 1 if the new input was 1. This gives you the first 2 rows in the first table. Filling in the rest is left as an exercise for you.

Note that the O column is just 1 if the next state is 0, as expected.