Архитектура уровня машины, реализуйте команды, используя другие

Question

Делая некоторую подготовку к собеседованиям, задавая вопросы об интервью, люди размещали на Glassdoor подобные должности. Я столкнулся с одним, я застрял и немного запутался.

Процессор только с 1 регистром и 2 слотами памяти. Имеет две инструкции SUB и STO. Реализуйте LOD, ADD и MOV, используя только следующее:

1. SUB a, memory1
2. SUB a, memory2
3. СТО память1, а
4. СТО память2, а

Я предполагаю, что STO - это магазин, а LOD - это загрузка. Таким образом, предполагается, что регистр начинается со значения 0? Если нет, я не уверен, как вообще начать, так как я не могу использовать вычитание с регистром, если в нем нет значения, могу ли я? Здесь немного потеряно.

Answer 1

Это в основном решение головоломки. Который не очень продуктивен как метод интервью, но он определенно стоит понять, что это так, и рассматривать его немного иначе, чем, например, методическая проблема программирования. В контексте интервью вы хотите прояснить, как вы подходите к пространству поиска и что вы думаете, а не просто выплевываете ответ.

В этом духе я подойду к этому немного более разговорчиво...

На вопрос о том, a изначально должен быть равен нулю, что бы мы делали, если бы начальное значение было произвольным? Как мы можем получить его равным нулю? Единственное вычисление, которое у нас есть, это вычитание... Как вы получаете гарантированный ноль от этого? Что ж X - X всегда ноль верно? Поэтому, если нам нужно, чтобы аккумулятор был нулевым, мы сохраняем его в ячейке памяти и затем вычитаем его обратно из аккумулятора. Почтовым условием для этого является то, что аккумулятор равен нулю.

Итак, отсюда мы можем видеть, что у нас есть одно ограничение - использование одной или обеих областей памяти в качестве временного хранилища. Это довольно большая проблема, но мы, вероятно, должны настаивать на том, чтобы составные последовательности команд использовали одну ячейку памяти в качестве временной, а другую - входной операнд. Остается открытым вопрос, могут ли все операции быть реализованы без разрушения ввода.

Начнем с загрузки, как это должно быть проще всего. Мы хотим:

LOD a, memory1 # a = *memory1 -- destroys value in memory2

Давай попробуем:

# zero a
STO a, memory2
SUB a, memory2
SUB a, memory1 # a == -memory1
# Save -memory1 and zero a again
STO a, memory2
SUB a, memory2 # a = 0
SUB a, memory2 # a = 0 - (-memory1)

Там есть LOD. Вполне может быть возможно быть более эффективным, но это должно начать вас.

ADD a, memory1 # a = a + *memory1 -- destroys value in memory2

Как и выше, мы будем использовать X - (-Y) == X + Y алгебраическая эквивалентность.

STO memory2, a # save a, call this "original_a"
SUB a, memory2 # a = 0
SUB a, memory1 # a = -*memory1
SUB a, memory2 # a = -*memory1 - original_a
# Save -*memory1 - original_a, then zero a
STO a, memory2
SUB a, memory2
SUB a, memory2 # a = -(-*memory1 - original_a) == *memory1 + original_a

И так далее...