arithmetic.py

# Using those electronic building blocs:
#
#   NOT GATE    NAND GATE     NOR GATE
#
#        GNR         GNR           GNR
#  a------<    a------<     a------< |
#  POW-ww-+-c  b------<     b------(-<
#              POW-ww-+--c  POW-ww-+-+--c
#
# We define "and" and "or":
"""
def and(a, b):
    return not (a nand b)

def or(a, b):
    return not (A nor b)
"""
# Also, my compute has RAM, each word is 8-bit
# ... and a CPU cache for my local variables
# ... and a conditional GOTO instruction, as if/elif/else, while and break

class BitsMixin:
    @staticmethod
    def n2b(n, size):
        return list(map(int, f'{n:0{size}b}'))

    @staticmethod
    def b2n(b):
        return int(''.join([str(int(b)) for b in b]), 2)

    def __getitem__(self, bit_no):
        if isinstance(bit_no, slice):
            return self._bits[bit_no]
        return self._bits[int(bit_no)]

    def __setitem__(self, bit_no, value):
        self._bits[int(bit_no)] = value

    def __int__(self):
        if self._bits[0]:
            raise NotImplementedError("Negative numbers have no representation yet")
        return self.b2n(self._bits)

    def __repr__(self):
        return tuple(map(int, self._bits))

    def __str__(self):
        return format(int(self), '08b')

    @property
    def size(self):
        return len(self._bits)

    def copy(self):
        return type(self)(list(self._bits))

    def __copy__(self):
        return self.copy()

    def __add__(self, other):
        return type(self)(self._bits + other)

class Word(BitsMixin):
    def __init__(self, bits):
        if isinstance(bits, int):
            bits = self.n2b(bits, 8)
        assert len(bits) == 8
        self._bits = bits

    @classmethod
    def zero(cls):
        return cls([0] * 8)

class Pointer(BitsMixin):
    def __init__(self, bits):
        assert len(bits) == 3
        self._bits = bits

    @classmethod
    def last(cls):
        return cls([1] * 3)

    @classmethod
    def first(cls):
        return cls([0] * 3)

    def incr(self):
        if not self[2]:
            self[2] = 1
            return False
        self[2] = 0
        if not self[1]:
            self[1] = 1
            return False
        self[1] = 0
        if not self[0]:
            self[0] = 1
            return False
        self[0] = 0
        return True

    def decr(self):
        if self[2]:
            self[2] = 0
            return False
        self[2] = 1
        if self[1]:
            self[1] = 0
            return False
        self[1] = 1
        if self[0]:
            self[0] = 0
            return False
        self[0] = 1
        return True

def eq(a, b):
    return a and b or not a and not b

def xor(a, b):
    return a and not b or not a and b

def add(a, b, r=0):
    return a and b or a and r or b and r, xor(xor(a, b), r)

def bt_incr(word):
    word = word.copy()
    i = Pointer.last()
    while True:
        if not word[i]:
            word[i] = 1
            break
        word[i] = 0
        if i.decr():
            print("overflow!!!")
            break
    return word

def bt_decr(word):
    word = word.copy()
    i = Pointer.first()
    while True:
        if word[i]:
            word[i] = 0
            break
        word[i] = 1
        if i.incr():
            print("underflow!!!")
            break
    return word

def shift_left(word, fill=0):
    word = word.copy()
    i = Pointer.first()
    j = Pointer.first()
    j.incr()
    while True:
        word[i] = word[j]
        i.incr()
        if overflow := j.incr():
            break
    word[i] = fill
    return word

def shift_right(word, fill=0):
    word = word.copy()
    i = Pointer.last()
    j = Pointer.last()
    j.decr()
    while True:
        word[i] = word[j]
        i.decr()
        if underflow := j.decr():
            break
    word[i] = fill
    return word

def bt_not(word):
    word = word.copy()
    i = Pointer.first()
    while True:
        word[i] = not word[i]
        if overflow := i.incr():
            break
    return word

def bt_and(word0, word1):
    word2 = Word.zero()
    i = Pointer.first()
    while True:
        word2[i] = word0[i] and word1[i]
        if overflow := i.incr():
            break
    return word2

def bt_or(word0, word1):
    word2 = Word.zero()
    i = Pointer.first()
    while True:
        word2[i] = word0[i] or word1[i]
        if overflow := i.incr():
            break
    return word2

def bt_eq(word0, word1):
    word2 = Word.zero()
    i = Pointer.first()
    while True:
        word2[i] = eq(word0[i], word1[i])
        if overflow := i.incr():
            break
    return word2

def bt_xor(word0, word1):
    word2 = Word.zero()
    i = Pointer.first()
    while True:
        word2[i] = xor(word0[i], word1[i])
        if overflow := i.incr():
            break
    return word2

def bt_add(word0, word1):
    word2 = Word.zero()
    i = Pointer.last()
    r = 0
    while True:
        r, word2[i] = add(word0[i], word1[i], r)
        if overflow := i.decr():
            break
    if r:
        print('overflow!!!')
    return word2

def bt_sub(word0, word1):
    return bt_add(word0, bt_two_complement(word1))

def bt_two_complement(word):
    return bt_incr(bt_not(word))


def test():
    for a, b in [Word.n2b(x, 2) for x in range(4)]:
        assert eq(a, b) == (a == b)
        assert xor(a, b) == (a != b)
    for a, b, c in [Word.n2b(x, 3) for x in range(8)]:
        assert add(a, b, c) == (a + b + c >> 1, a + b + c & 1)
    for word0, word1 in [(Word(x), Word(y)) for x in range(8) for y in range(8)]:
        assert int(bt_and(word0, word1)) == (int(word0) & int(word1))
        assert int(bt_or(word0, word1)) == (int(word0) | int(word1))
        assert int(bt_xor(word0, word1)) == (int(word0) ^ int(word1))
        assert int(bt_add(word0, word1)) == (int(word0) + int(word1))
    for word in [Word(x) for x in range(8)]:
        assert int(shift_left(word)) == (int(word) << 1)
        assert int(shift_right(word)) == (int(word) >> 1)

test()

print(int(bt_sub(Word(17), (Word(5)))))