Saturday, February 6, 2010

Interesting HW interview question... Serial binary input divisible by 5

I'm in California at the third round of interviews and I'm asked a question that baffled me. Given a serial input of a binary number, write a state machine that tells if that value is divisible by 5.

I first solved the problem thinking the input was MSB first. This is pretty trivial. 5 states and some very simple movements. Then it was clarified that they wanted it solved LSB first. I thought about it but I could not come up with a solution.

It is now the next day and I approached the problem again. I have a good and clear solution, but I'd love to know if there is a better one.

WARNING - Solution below:


A single bit, in any location, when converted to decimal will always end in either 2, 4, 8, or 6 except of course the least significant bit which is 1.
1, 2, 4, 8, 16, 32, 64, 128, 256...
1, 2, 4, 8, 6, 2, 4, 8, 6...
A divide by 5 problem at any given time can be in one of five situations. It's either 0, 1, 2, 3, or 4 from being divisible by 5. Ie: it is 0 and is divisible, or 1 and needs another 4, or 2 and needs another 3...

By combining both of these ideas you can build a state machine with 20 states that easily solves this problem. It's like 5 small 4-stated machines. The 4-stated machine keeps moving between 2, 4, 8, and 6 when there's a 0 input, and moves to one of the other machines when there is a 1. Of course you need an extra start state to deal with the first bit. And anytime you are in the 0 4-stated machine then the value is divisible.

Best way to explain is by example:
current value, add value (c, a) where c goes from 0 to 4 and a is 2, 4, 8, or 6.

Starting in first bit state:
Value that will be given is 25 (11001).
1: First bit state moves to (1, 2) since current value is 1 and next bit will add 2.
0: (1, 2) moves to (1, 4) since current value is still 1 and next bit will add 4.
0: (1, 4) moves to (1, 8) since current value is still 1 and next bit will add 8.
1: (1, 8) moves to (4, 6) since current value is now 4 (9 divided by 5 leaves a remainder of 4) and next bit will add 6.
1: (4, 6) moves to (0, 2) since current value is now 0 (10 divided by 5 leaves a remainder of 0) and next bit will add 2.

That's it.

6 comments:

  1. Its so interested! It would be usefull if you could give me a general solution for the reverse way ( MSB first....that commentes as trivial).
    Thanks in advance!

    ReplyDelete
  2. its an unusual question but would be fun to design it.

    ReplyDelete
  3. you can do it with 5 state, each state represents the reminder, it can be 0,1,2,3 or 4. if you get a 0 the number is mulitplayed by two and if a 1 the number is multiplied by two and added a one. so the only way to get a devition is from remainder 2 and recive a 1, or remaider of 0 and recive a 0. and connect in this way the oner states.

    ReplyDelete
  4. how would circuit look like if multiple of 5 has be detected in running stream bits

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  6. Beautiful solution!

    ReplyDelete