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 XORin terms of the subtract and branch if equal or lower (subleq) operator.https://en.wikipedia.org/wiki/One_instruction_set_computerC.M. Punter 2016"""import randomdef my_sub(a: int, b: int) -> int:    return a - bdef my_leq(a: int, b: int) -> bool:    return a <= b# now we write all other functions in terms of the above two functionsdef 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 cdef 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 cdef my_mod(a: int, b: int) -> int:    while my_leq(b, a):        a = my_sub(a, b)    return adef 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 cdef 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 cdef 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 cdef 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))

There's a more efficient way of doing this, this requires the use of looping operators and the construction of a less than (but not equal to) zero function, which you will have to provide yourself. The idea is that you can check a single bit (the top bit) for it being negative, you can then use this to construct an OR, AND or XOR.

/* Author: Richard James Howe * Email:[email protected]  * Using primitives available in SUBLEQ to perform bitwise operations */#include <stdio.h>#include <stdint.h>#include <stdlib.h>#define N   (16)#define TST (9999)typedef int16_t uword_t;typedef int16_t  word_t;static uword_t zlt(uword_t z) {    return ((word_t)z) < 0 ? 0xFFFFu : 0;}static uword_t add(uword_t a, uword_t b) {    return a - (uword_t)((uword_t)0 - b);}static uword_t lshift1(uword_t a) {    return add(a, a);}static uword_t b_or(uword_t a, uword_t b) {    uword_t r = 0;    for (size_t i = 0; i < N; i++) {        r = lshift1(r);        if ((uword_t)(zlt(a) + zlt(b)) != (uword_t)0u)            r++;        a = lshift1(a);        b = lshift1(b);    }    return r;}static uword_t b_xor(uword_t a, uword_t b) {    uword_t r = 0;    for (size_t i = 0; i < N; i++) {        r = lshift1(r);        if ((uword_t)(zlt(a) + zlt(b)) == (uword_t)0xFFFFu)            r++;        a = lshift1(a);        b = lshift1(b);    }    return r;}static uword_t b_and(uword_t a, uword_t b) {    uword_t r = 0;    for (size_t i = 0; i < N; i++) {        r = lshift1(r);        if ((uword_t)(zlt(a) + zlt(b)) == (uword_t)0xFFFEu)            r++;        a = lshift1(a);        b = lshift1(b);    }    return r;}static uword_t rnd(void) {    return rand();}int main(void) {    int pass_or = 1, pass_xor = 1, pass_and = 1;    for (long i = 0; i < TST; i++) {        uword_t a = rnd(), b = rnd();        uword_t rn = a | b;        uword_t rb = b_or(a, b);        if (rb != rn) {            printf("or fail %x %x -- expected %x got %x\n", a, b, rn, rb);            pass_or = 0;        }    }    printf("or %s\n", pass_or ? "pass" : "FAIL");    for (long i = 0; i < TST; i++) {        uword_t a = rnd(), b = rnd();        uword_t rn = a ^ b;        uword_t rb = b_xor(a, b);        if (rb != rn) {            printf("xor fail %x %x -- expected %x got %x\n", a, b, rn, rb);            pass_xor = 0;        }    }    printf("xor %s\n",  pass_xor ? "pass" : "FAIL");    for (long i = 0; i < TST; i++) {        uword_t a = rnd(), b = rnd();        uword_t rn = a & b;        uword_t rb = b_and(a, b);        if (rb != rn) {            printf("and fail %x %x -- expected %x got %x\n", a, b, rn, rb);            pass_and = 0;        }    }    printf("and %s\n",  pass_and ? "pass" : "FAIL");    printf("done %s\n", pass_or && pass_xor && pass_and ? "pass" : "FAIL");    return 0;}

See also:

• https://gist.github.com/howerj/a08b127e944df30deaf0a4fec1a6d5be (where this code come from)
• https://github.com/howerj/subleq (a usage of this code for a Forth interpreter)
• https://gist.github.com/howerj/4e0741370bd22b3181443bf3e0ba6697 (for implementing the comparison operators)

• Isn't((word_t)z) < 0 a less-than rather than less-or-equal operation? I guess there's some well-known way to implement that and== 0xFFFEu in terms ofsubleq, but you don't mention it in your answer.

  – Peter Cordes

  CommentedFeb 18, 2021 at 21:56
• Yes, it is, you have to implement that yourself, equality and inequality are fairly easy to implement, so are looping, most SUBLEQ assemblers already implement such constructs. So I left them out. However, less than zero (and not equal to) is a little more tricky, but it is possible. I'll get around to adding "< 0".

  – howerj

  CommentedFeb 18, 2021 at 22:08
• I've just added a gist for the comparison operators, so you can see how they are implemented.

  – howerj

  CommentedApr 6, 2023 at 21:40

• assembly
• bitwise-operators
• cpu-architecture