Bitwise operations in subleq

Question

Many pages demonstrate synthesising more complicated arithmetic and logical operations out of the single subleq instruction. I have not managed to find any pages discussing implementations of bitwise operations such as NAND, XOR ... Etc

Personally I haven't found a method that implements any of those operations (except for NOT) without using loops. Is there a neat way of doing it?

Answer 1

I've written a little demonstration program. I did use loops to implement some of the operators.

"""
This program demonstrates that you can write the bit operators AND, OR and XOR
in terms of the subtract and branch if equal or lower (subleq) operator.
https://en.wikipedia.org/wiki/One_instruction_set_computer

C.M. Punter 2016
"""
import random


def my_sub(a: int, b: int) -> int:
    return a - b


def my_leq(a: int, b: int) -> bool:
    return a <= b


# now we write all other functions in terms of the above two functions

def my_add(a: int, b: int) -> int:
    return my_sub(a, my_sub(0, b))


def my_mul(a: int, b: int) -> int:

    c = 0

    while my_leq(1, b):
        c = my_add(c, a)
        b = my_sub(b, 1)

    return c


def my_div(a: int, b: int) -> int:

    c = 0

    while my_leq(b, a):
        c = my_add(c, 1)
        a = my_sub(a, b)

    return c


def my_mod(a: int, b: int) -> int:

    while my_leq(b, a):
        a = my_sub(a, b)

    return a


def my_and(a: int, b: int) -> int:

    c = 0
    d = 1

    while my_leq(1, my_mul(a, b)):

        # we look at the first bit of a and b by checking if the number is odd or even
        # for this we use the modulo operator (a mod 2 and b mod 2)
        # this results in a 1 if the number is odd (which means the first bit is 1)
        # and 0 if the number is even (which means the first bit is 0)
        # multiplying those two numbers gives the and-operator for the first bit of a and b
        # the other bits are handled by bit-shifting a and b
        # this is equivalent to multiplying (left-shift) or dividing (right-shift) by 2

        c = my_add(c, my_mul(my_mul(my_mod(a, 2), my_mod(b, 2)), d))
        d = my_mul(d, 2)
        a = my_div(a, 2)
        b = my_div(b, 2)

    return c


def my_or(a: int, b: int) -> int:

    c = 0
    d = 1

    while my_leq(1, my_add(a, b)):
        if my_leq(1, my_add(my_mod(a, 2), my_mod(b, 2))):
            c = my_add(c, d)

        d = my_mul(d, 2)
        a = my_div(a, 2)
        b = my_div(b, 2)

    return c


def my_xor(a: int, b: int) -> int:

    c = 0
    d = 1

    while my_leq(1, my_add(a, b)):
        e = my_add(my_mod(a, 2), my_mod(b, 2))
        if my_leq(e, 1):
            c = my_add(c, my_mul(e, d))

        d = my_mul(d, 2)
        a = my_div(a, 2)
        b = my_div(b, 2)

    return c


def test(a: int, b: int):
    assert a & b == my_and(a, b)
    assert a | b == my_or(a, b)
    assert a ^ b == my_xor(a, b)

for i in range(1000):
    test(random.randint(0, 1024), random.randint(0, 1024))