Software, technology, sysadmin war stories, and more. Feed
Friday, June 8, 2012

Delayed solutions: pop the stack

For whatever reason, I seem to remember a lot of things. Sometimes, details of projects and other things which were "pushed onto the stack" will pop back out much later. This leads to some scenarios where I remember someone's problem and have a solution but the original situation is (probably) no longer valid. At that point, it's largely an academic exercise since the original use case has evaporated.

One such example starts in the days when I was bored in class and wrote a proof of concept BBS on my TI-85 calculator. It was a bulletin board in the traditional sense, where people could send short messages to each other. It was not intended to reflect what BBSes had become over the years with their massive file sections, games (doors) and such.

Anyway, as detailed in my post from last summer, my implementation used matrix logic to keep track of who was a valid user and what their password may have been. I also used some other matrix stuff to figure out which mail slots were active, and who the sender and recipient were, and all of that.

Around this time, someone found out I was doing this and wanted to try doing the same thing on his calculator. Trouble was, he had the TI-81 which was even more limited in what it could do within the scope of a program. According to him, matrix operations were right out. That meant my design was off the table and he would have to get clever. I suggested using numeric values and flipping bits to keep track of things. Using OR to set a bit and AND to test it would let him at least know if a given slot was in use, at least up to the bit size of that variable. I figured if he could get 8 or 16 bits (slots) out of it, that would be plenty.

This brought up yet another problem. Again, according to him, the TI-81 didn't have bitwise operators. There was no way to just sling an AND or OR in the right place to do what needed to be done. At this point, I considered it too far gone and basically said he was on his own with this one.

We went through all of this during a chance encounter in the hallway between classes. It was a conversation which lasted at most five minutes and ended with him needing to go off and experiment on his own. Still, somehow, it stuck in my head.

About six years later, I was just relaxing one evening and this thing popped back up out of nowhere. Apparently I had been thinking of the patterns you get when looking at ascending binary progressions of numbers. Bit 0 flips every row while bit 1 does two rows on, then two rows off, and repeats. Bit 2 is four on, then four off, and it just keeps going like this. Once you've stared at a list of binary numbers for a while, the pattern becomes clear.

Somehow, this awakened the memory of that chance conversation, and I realized that somehow it could all be pulled together. That guy with the TI-81 could get his bitwise operations using nothing more than a few obvious math functions which were almost certainly in his calculator.

I wound up arriving at this: a = num / 2 ^ bit, where num is the number with all of the bits bound up in it, and bit is the bit number to check, starting with 1. This assumes that / is integer division, by the way.

If a is less than 1, then the answer is no.

If a is odd, then the answer is yes.

If a is even, then the answer is no.

So let's say we want to check to see whether slot number 3 is active. We can try using that with a few made up values:

num = 0, a = 0 / 2^3 ... a == 0, which is less than one --> false.

( same for 1, 2, 3, 4, 5, 6, 7 )

num = 8, a = 8 / 2^3 ... a == 1, which is odd --> true.

( same for num = 9, 10, 11, 12, 13, 14, 15 )

num = 16, a = 16 / 2^3 ... a = 2, which is odd --> false.

It just keeps going like this, cycling on and off much like the pattern you see when looking at just one column of a binary count.

Is this exceptionally stupid and dull? Definitely. The whole point was to see whether bitwise stuff could be done without having the usual tools, and this made me think that it could. You'd have to be very careful with all of this bit wrangling, but it should be possible.

I never tried to use this, so it's possible there are gaping holes in this and the people who actually "get" math will write in and point them out. Feel free to write in if you want, but realize this has never been my strong suit. I just spotted a pattern and found a way to apply it.

Ultimately, it looks like I (apparently) solved a problem for a theoretical calculator-based BBS which was never written in the first place, and I did it six years later. This little anecdote then waited around on ice for many more years before escaping into the wild in the form of this post.

That's my wacky memory for you.