Реализация логического сдвига вправо
Поэтому я работаю над проектом nand2tetris и хочу реализовать логическое смещение вправо на программном уровне, поскольку аппаратное обеспечение не поддерживает его. Я знаю, что смещение вправо логично - это деление на два. Таким образом, мой первый шаг к реализации этого будет подсчитывать, сколько раз я смог вычесть 2 из исходного значения, прежде чем значение станет 0 или отрицательным. Аналогично, если число было отрицательным. Но я нашел сценарий, где он не работает. Я хочу сдвинуть вправо -27139. Итак, двоичное значение после сдвига равно 19199. Это должно быть 19198. Таким образом, я ищу новый способ реализации сдвига. Я могу и ценности, или ценности, складывать и вычитать, и это все, что у меня есть в моем распоряжении.
Спасибо за помощь.
OSFTW
Вот код, который я имею на ассемблере реализации Hack:
//============================================================
// SLR: Shift Logical Right (by 1)
//============================================================
(SLR)
@SLR.1 // Load value
D=M
@SLR.2
M=0 // Clear variables
@SLR_POSITIVE_LOOP // If value is positive, go to the positive loop
D;JGT
(SLR_NEGATIVE_LOOP)
@SLR.1 // Add 2 to value, since it's negative
M=M+1
M=M+1
@SLR.1 // If initial value was negative and current value is positive or zero, jump out of loop
D=M
@SLR_NEG
D; JGE
@SLR.2 // If value is negative, add 1 to SLR.2 (we're dividing)
M=M+1
@SLR.1 // If value is less than 0, restart the loop
D=M
@SLR_NEGATIVE_LOOP
D; JLT
(SLR_NEG)
@SLR.2
D=M
D=!D // Invert the result
D=D+1 // Add 1 to finish converting
@32767 // And it with 0111111111111111 to clear the sign bit
D=D&A
@SLR.2
M=D // Set value
@SLR_END // Jump to end of loop
0;JMP
(SLR_POSITIVE_LOOP)
@SLR.1 // Subtract 2 from value
M=M-1
M=M-1
@SLR.1 // If initial value was positive and current value is negative or zero, jump out of loop
D=M
@SLR_END
D; JLE
@SLR.2 // If value is still positive, add 1 to SLR.2 (we're dividing)
M=M+1
@SLR.1 // If value is greater than 0, restart the loop
D=M
@SLR_POSITIVE_LOOP
D; JGT
(SLR_END) // Loop is over. Set value of SLR.1 to that of SLR.2, for return purposes
@SLR.2 // Place result in correct place
D=M
@SLR.1
M=D
@SLR.0 // Return to calling function
A = M
0; JMP
5 ответов
Логический сдвиг числа влево или вправо равняется копированию Nn битов из одного слова из N битов в другое. Таким образом:
unsigned int a = 0x1321;
unsigned int b = 0;
unsigned int mask1 = 1;
unsigned int mask2 = 1 << n; // use repeated addition for left shift...
int i;
for (i = 0; i < N-n; i++) {
if (a & mask2)
b|= mask1;
mask1 += mask1;
mask2 += mask2;
}
Поменяв местами mask1 и mask2, можно реализовать сдвиг влево (только с битовыми операциями)
В соответствии с природой курса Nand2Tetris в этом ответе я попытался подвести черту, приводя примеры методов кодирования на ассемблере Hack и общих алгоритмов, но оставляя окончательный код в качестве упражнения.
Hack ALU не имеет никаких путей данных, которые соединяют бит N с битом N-1. Это означает, что сдвиги вправо и повороты должны выполняться с использованием поворотов влево. (Примечание: слева = старшие значащие биты, справа = младшие значащие биты)
Сдвиг влево легко, так как это просто умножение на 2, которое само по себе является просто сложением. Например:
// left-shift variable someVar 1 bit
@someVar // A = address of someVar
D = M // D = Memory[A]
M = M + D // Memory[A] = Memory[A] * 2
Поворот влево немного сложнее. Вам нужно сохранить копию самого левого бита и переместить его в самый правый бит после выполнения умножения. Тем не менее, обратите внимание, что у вас есть копия исходного значения "someVar" в регистре D, и вы можете тестировать и переходить на основании его значения - если самый левый бит D равен 1, то D будет меньше нуля. Кроме того, обратите внимание, что после умножения "someVar" на 2, его самый правый бит всегда будет равен 0, что позволяет легко устанавливать его без изменения других битов.
Как только вы повернули налево, повернуть вправо просто; если вы хотите повернуть влево на N битов, вместо этого вы должны повернуть вправо на 16 битов. Обратите внимание, что это предполагает N в диапазоне 0-15.
Сдвиг вправо - самая сложная операция. В этом случае вам нужно сначала повернуть вправо, а затем сгенерировать маску, в которой старшие N бит установлены в ноль. Вы И результат правого поворота с маской.
Основной способ создания маски - начать с -1 (все установленные биты) и добавить его к себе N раз; это делает самые правые N битов маски 0. Затем поверните это 16-N раз влево, чтобы переместить все 0 битов в крайние левые N битов.
Тем не менее, это много циклов, и при программировании на ассемблере сохранение циклов - это то, что нужно. Есть несколько методов, которые вы можете использовать.
Первый использует адресную арифметику для реализации эквивалента оператора case. Для каждого из 16 возможных значений поворота необходимо загрузить 16-битное значение маски в регистр D, а затем перейти к концу регистра. Вы должны быть осторожны, потому что вы можете загрузить только 15-битные константы, используя @instruction, но вы можете выполнить загрузку и безусловный переход в 6 инструкциях (4 для загрузки полной 16-битной константы и 2 для перехода).
Поэтому, если у вас есть 16 из них, начиная с местоположения (CASE), вам просто нужно умножить N на 6, добавить его в @CASE и перейти в это местоположение. Размышляя о том, как умножить на 6, имейте в виду одну из действительно симпатичных особенностей набора команд HACK; Вы можете хранить результаты операции ALU одновременно в нескольких регистрах.
Однако наиболее эффективным решением является предварительное вычисление таблицы маски. Во время инициализации программы вы генерируете 16-битные маски и сохраняете их в некотором фиксированном месте в памяти, затем вы можете просто добавить N к адресу начала таблицы и прочитать маску.
Поскольку процессор HACK не может получить доступ к ПЗУ программы, кроме как для извлечения инструкций, вы не можете сохранить таблицу в ПЗУ, вам нужно использовать несколько инструкций для каждой записи таблицы, чтобы загрузить значение в регистр D и затем сохранить его в ОЗУ., В итоге я написал простой скрипт на python, который генерирует код для инициализации таблиц.
Будет проще, если вы будете рассматривать значение смещения как беззнаковое, поскольку логическое смещение вправо не сохранит знак в любом случае. Затем вы просто вычитаете 2 несколько раз, пока результат не станет меньше 2, и в этом случае число вычитаний будет вашим частным (то есть смещенным вправо значением).
Пример реализации в C:
int lsr(int valueToShift)
{
int shifted = 0;
uint16_t u = valueToShift;
while (u >= 2) {
u -= 2;
shifted++;
}
return shifted;
}
Вы должны использовать двоичный или шестнадцатеричный, так как использование десятичного знака затрудняет представление числового представления.
Если у вас есть арифметический сдвиг, но не логический сдвиг, наиболее очевидным решением будет очистить старшие биты, если он отрицательный
int LogicalRightShift(int x, int shift)
{
return (x >> shift) & ((1U << (CHAR_BIT*sizeof(x) - shift)) - 1);
// or
return (x >> shift) & (~((~0) << (CHAR_BIT*sizeof(x) - shift)));
}
Если у вас нет арифметического сдвига вправо, вы можете копировать его постепенно
int LogicalRightShift(int x, int shift)
{
// assuming int size is 32
int bits[] = { 0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80,
0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000,
0x10000, 0x20000, 0x40000, 0x80000, 0x100000, 0x200000, 0x400000, 0x800000,
0x1000000, 0x2000000, 0x4000000, 0x8000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000
}
int res = 0;
for (int i = 31; i >= shift; i++)
{
if (x & bits[i])
res |= bits[i - shift];
}
return res;
}
Другой способ - это многократное деление на 2. Или вы можете хранить силы 2 в справочной таблице и делить на эту силу. Таким образом, он может быть медленнее, чем метод битового копирования, описанный выше, если у вас нет аппаратного делителя, но все же гораздо быстрее, чем вычитать тысячи раз, как ваш метод. Чтобы сдвинуть -27139 (38397) вправо на 1 бит, вам нужно вычесть 2 из числа 9599 раз и даже больше, если число больше или если вам нужно сдвинуть другое количество бит
Более быстрый способ может заключаться в использовании сложения. Для грубого примера:
uin32_t LSR(uint32_t value, int count) {
uint32_t result = 0;
uint32_t temp;
while(count < 32) {
temp = value + value;
if(temp < value) { // Did the addition overflow?
result = result + result + 1;
} else {
result = result + result;
}
value = temp;
count++;
}
return result;
}
Основная идея состоит в том, чтобы сдвинуть 64-разрядное целое число без знака влево на 32 числа, а затем вернуть старшие 32 бита.
В сборке большая часть кода выше (ветви и т. Д.), Надеюсь, станет чем-то вроде add value, value затем add_with_carry result, result,