Hardware interview practice
Track divisibility by three in an MSB-first stream
Receive a binary number most-significant bit first and report whether the accepted prefix is divisible by three. Use the minimum number of remainder states and support valid gaps plus an explicit start-of-number marker.
Reviewed example
Work through one case
Input
start an MSB-first number with accepted bits [1,1,0] (binary 6)Expected output
remainders=[1,0,0]; divisible outputs=[0,1,1] with out_valid on each accepted prefixApplying (2r+b) mod 3 gives the minimum three-state remainder machine and consumes the start bit as part of the new number.
What to cover
Requirements
- Use one state for each remainder 0, 1, and 2.
- For each accepted bit b, update remainder with (2 x remainder + b) mod 3.
- start resets the arithmetic history before consuming the current valid bit.
- Pulse out_valid only when a bit is accepted, so reset, an empty stream, or a valid gap is not mistaken for a new result.