Как я могу найти четные числа, используя MARIE?

Question

Я работаю над проектом, но я застрял. Я пытаюсь написать фрагмент кода, который проверяет, является ли данное число четным, вычитая его на 2 (данное число не может быть больше 6). Если он четный, то печатается 0, если нечетный, печатается 1.

    int count=input.nextInt()
    int parity=0

    while (count>0)
        count=count-2;
        if (count<0) {
            parity=parity+1;
            System.out.print(parity);
        }
        else if (count==0) {
            System.out.println(parity);
        }

^^ Это мой код Java, который я пытался перевести на язык MARIE, но ничего не работает.

Я бы опубликовал свой код MARIE, но я чувствую, что это слишком запутанно:/

Answer 1

Вам нужно только проверить младший бит на 0 / не ноль. Нормальные архитектуры имеют инструкцию AND, которая сделает это простым, но MARIE имеет только add / sub (и сравнивает для большего или меньшего).

Но да, ваш цикл будет работать, принимая O(n) итераций для числа n, Было бы намного проще реализовать в asm, если бы вы написали это как do{}while() петля, как

n = input;
do {
    n-=2;      // sub
}while(n>=0);  // skipcond
// n==0 or -1 for even or odd

---

Вы можете сделать это в O(log(n)) операции с использованием add как сдвиг влево: AC+AC это то же самое, что AC << 1, Сделайте это 15 раз, чтобы сдвинуть младший бит на верх, а остальные биты вывести. (Аккумулятор AC имеет ширину 16 бит).

К сожалению, это очень неудобно для MARIE, потому что ADD работает только с операндом источника памяти, а не с AC, Поэтому вам нужно где-то хранить переменный ток, чтобы использовать его как операнд источника памяти для ADD.

(Это определенно не стоит, если вы знаете, что ваш ввод находится в диапазоне 0..6. В этом случае он занимает не более 3 итераций n-=2 цикл, чтобы получить результат, против всегда 15 для этого. Но с неограниченными входами, n-=2 версия может потребовать 32768 итераций! Или 16384, если мы ограничим это целыми числами с положительными знаками; n-=2 версия даже не работает для отрицательных целых чисел)

Так, например:

/ Assuming input in AC

Store tmp
Add   tmp

Store tmp
Add   tmp
/ repeat this 13 more times, for a total of 15 ADDs
/ inconvenient to make a loop because Marie only has 1 register
/ but would be smaller for this many shifts

/ AC = input << 15

/ AC is non-zero for odd, zero for even.  You could just store that directly if you want.

/ If you want to branch on it here, or in some code that reloads that 0 / non-zero result
SkipCond  400     / jump over next insn if AC==0
jump     odd_input     / or this can be a store instruction
/ else fall through when input was even: input&1 == 0


tmp, dec 0

Цикл будет иметь смысл, особенно если вы развернули его на 2 или около того. Если бы переменная составляла всего 8 бит, то для полного развертывания потребовалось бы всего 7 инструкций STORE/ADD, но 15 - это немного.