Bitwise Scanner

Bitwise Scanner is a bitwise language created by User:A. It is based on scanning a bitwise tape.

Commands

Command	Description
(statements)	Execute the code block composed of the statements if the current bit is 0.
{statements}	Execute the code block composed of the statements if the current bit is 1.
[statements]	Sequentially query the bitwise tape, from the lowest digit to the highest digit, executing the statements.
~	Multiply the current bit by -1 and add 1. Equivalent to flipping the bit.
X	Stop the scanning.

The increment procedure

000->001
001->010
010->011
011->100

We can conclude that the algorithm is(without doing math):

If the lowest digit is zero,
    Flip the lowest bit
Otherwise(if the lowest bit is 1),
    scan from the lowest digit to the highest digit:
        If the current bit is 1,
            flip this bit
        Otherwise (current bit is 0)
            flip this bit and stop scanning

This can be achieved in Bitwise Scanner like this:

(~){[{~}(~X)]}

The decrement procedure

111->110
110->101
101->100
100->011
011->010
010->001

The main algorithm for this is:

If the lowest bit is 1:
    Flip the lowest bit
Otherwise(if the lowest bit is 0):
    Scan the binary array:
        If the current bit is 0:
            Flip the current bit
        Otherwise:
            Flip the current bit and stop scanning

This can be achieved as:

{~}([(~){~X}])

Computational Class

Bitwise Scanner is in the class of finite state automata since it can store state in the form of where in the program it is executing. Take, for instance, this program:

([{~}]){[(~)]}

This program has the effect of setting all bits to be the same as the first bit. This necessarily means that this program stores state, one bit in this case. The amount of state that a Bitwise Scanner program can store is finite and determined by the length of the program.

The implementation below is non-canonical since it is not from the original author, but its looping construct (scan) always ends at the end of input, making it total. The behavior of scan when encountering the last bit of input is unspecified. We can assume it loops (in which case it is FSA) or it halts (in which case it is total).

Interpreter

• Common Lisp implementation of the Bitwise Scanner programming language.