Реализация логического сдвига вправо

Question

Итак, я работаю над проектом 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 

Answer 1

Логический сдвиг числа влево или вправо равен копированию N-n бит из одного слова из 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; 
} 

Swapping mask1 и mask2 будут реализовывать сдвиг влево (только с побитовыми операциями).

Answer 2

Это становится проще, если рассматривать значение сдвига в качестве знака, так как логический сдвиг вправо не будет сохранять знак в любом случае. Затем вы просто вычитаете 2 до тех пор, пока результат не станет меньше 2, и в этот момент количество вычитаний будет вашим фактором (т. Е. Правым сдвинутым значением).

Пример реализации в C:

int lsr(int valueToShift) 
{ 
    int shifted = 0; 
    uint16_t u = valueToShift; 

    while (u >= 2) { 
     u -= 2; 
     shifted++; 
    } 

    return shifted; 
} 

Answer 3

Вы должны использовать двоичный или шестнадцатеричный поскольку использование десятичной делает его трудно представить себе представление чисел.

Если у вас есть арифметический сдвиг, но не логический сдвиг, наиболее очевидным решением было бы очищая верхние биты, если он отрицательный

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 раз и даже больше, если число больше или если вам нужно сдвинуть другое количество бит

Answer 4

Более быстрый способ может быть использование дополнение. Для сырого Например:

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.

Answer 5

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

Hack ALU не имеет путей передачи данных, которые соединяют бит N с битом N-1. Это означает, что сдвиги вправо и вращение должны выполняться с помощью левого поворота. (Примечание: left = наиболее значимые бит, справа = младшие значащие бит)

С левым сменом легко, так как это просто умножение на 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 бит. Обратите внимание, что это предполагает 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 к адресу начала таблицы и прочитать маску.

Поскольку CPU HACK не может получить доступ к программному ПЗУ, кроме как для получения инструкций, вы не можете сохранить таблицу в ПЗУ, вы должны использовать несколько инструкций для записи в таблице для загрузки значения в регистр D, а затем сохраните его в ОЗУ. В итоге я написал простой скрипт python, который генерирует код для инициализации таблиц.