Movatterモバイル変換

You are notlogged in. Your edit will be placed in a queue until it ispeer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

Bitwise operations in subleq

Many pages demonstrate synthesising more complicated arithmetic and logical operations out of the singlesubleq 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*

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))

tips on writing great answers.

Draft saved

Draft discarded

Edit Summary*

Cancel

Add a comment |

How to Edit

Correct minor typos or mistakes
Clarify meaning without changing it
Add related resources or links
Always respect the author’s intent
Don’t use edits to reply to the author

How to Format

create code fences with backticks ` or tildes ~
```
like so
```
add language identifier to highlight code
```python
def function(foo):
print(foo)
```
put returns between paragraphs
for linebreak add 2 spaces at end
_italic_ or**bold**
indent code by 4 spaces
backtick escapes`like _so_`
quote by placing > at start of line
to make links (use https whenever possible)
<https://example.com>
[example](https://example.com)
<a href="https://example.com">example</a>

formatting help »
answering help »

How to Tag

A tag is a keyword or label that categorizes your question with other, similar questions. Choose one or more (up to 5) tags that will help answerers to find and interpret your question.

complete the sentence:my question is about...
use tags that describe things or concepts that areessential, not incidental to your question
favor usingexisting popular tags
read the descriptions that appear below the tag

If your question is primarily about a topic for which you can't find a tag:

combine multiple words into single-words with hyphens (e.g.python-3.x), up to a maximum of 35 characters
creating new tags is a privilege; if you can't yet create a tag you need, then post this question without it, thenask the community to create it for you

popular tags »

Movatterモバイル変換

Collectives™ on Stack Overflow

Bitwise operations in subleq

Answer*