How would I go about finding the max length of consecutive 1s in a variable-length binary string from 0-19 characters in LC3?

Question

I am working on a program in LC3 to find the longest run of '1's in a variable-length binary string with a maximum of 19 characters. I have my loop to get the input but am stuck on how to count the consecutive length of '1's. I have found similar problems in other languages but having trouble trying to figure this out in LC3. Any help would be appreciated.

Answer 1

You need an algorithm.  Algorithms are language independent.

It is a mistake to think about algorithms as being specific to some language, e.g. in LC-3 assembly.

We don't have to think in assembly to make an assembly program.  Create your algorithm in a language you know, preferably C since it is closer to assembly than others, and then translate each statement/expression of your algorithm into assembly.  If you're having problems with that you can ask here: how do I do an if-statement in assembly, or how do I do a loop in assembly; of course, those questions already have answers on this website.

---

For this, a state machine is appropriate.  Two states: accumulating and not accumulating.

Whenever you see a 0 you go to not accumulating (and if already in this state, then stay in this state).  Whenever you see a 1 you add 1 to the counter of how many 1's (and if already there, stay in this accumulating state).

Also when you see a 0, check the counter of 1's and if it is larger than current max, capture that value as new max.  Also as part of seeing the 0's, reset the 1's counter for the next time you see some 1's.

Alternately, each time the counter of run of 1's is incremented, see if larger than max, and capture.  There's a number of variations that will all work.

So, two states are needed and two variables: current max of 1's and current run count of 1's.

---

A simple state machine like that can be had by having a boolean variable or state variable that says what state the program is in.

But even that is unnecessary and overkill for something this simple, as states can be represented by different sections of code.  If the program is in a first section, it is in the not accumulating state, and if in the second section of code it is in the accumulating state.

The two sections of code each look at the next input and either stay in the state, doing what they do, or switch to the other state.

Both end (to a third state, the ending state) after ending criteria has been reached (e.g. 19 chars, or newline, or whatever).

At reaching the end, the transition code that checks if the current 1's are larger than the current max should also run.