Построение шестнадцатеричного числа путем сдвига, инвертирования и добавления +/- 1
Я пытаюсь сохранить число 0xFD00 в регистре (архитектура MIC-1). Имеются регистры:
- 0
- +1
- -1
- АМАСК: 0x0FFF
- СМАСК: 0x00FF
Я могу делать сдвиги влево, вправо и инверсию. Также можно добавить такие значения, как SMASK + SMASK или AMASK + (-1). Я могу получить 0xF000 с инверсией (AMASK), но я не уверен, как получить 0xFD00 без слишком большого количества шагов.
3 ответа
На данный момент наиболее эффективной последовательностью является ответ @Falk Hüffner , 3 операции. (Хотя это связано с
+который не добавляет +1 или -1 или значение к себе).
Этот ответ показывает способ, который требует 4 операций, явно упомянутых в заголовке вопроса.
0xFD это
0b11111101. Таким образом, у него есть куча смежных битов и еще один случайный установленный бит. Один простой способ был бы
- начните со всех единиц (,
~0, или же0 - 1) - сдвиг влево на 2, чтобы получить
...11111100 - добавьте 1, чтобы получить
...11111101(0x...FD) - перейти к началу регистра, сдвигая младшие 0 и сдвигая старшие 1, оставляя
0xFDвверху с 8 нижними нулями.
Я не знаю MIC-1, но из вашего описания похоже, что он может делать эти шаги. Если он может смещаться только на 1 позицию за раз, потребуется всего 2 + 8 инструкций сдвига. Могут быть другие способы построить эту константу более эффективно, может быть, с чем-то, о чем я не думаю, или, может быть, с некоторыми возможностями, которые есть у машины.
Использование преимуществ AMASK/SMASK и того, как распространение переноса сложения/подпрограммы может инвертировать последовательность битов 1/0 соответственно, наряду с наблюдением Аки о том, что
~0xfd00знак равно
0x02ff, мы можем сделать следующее:
initial AMASK = 0x00FF
AMASK += 1 (0x0100)
AMASK += AMASK (0x0200) (left shift)
AMASK += SMASM (0x02FF)
NOT AMASK (0xFD00)
См. https://catonmat.net/low-level-bit-hacks для хорошего введения в виды махинаций, которые вы можете получить с побитовыми операциями. (Хотя многие из них также требуют И, ИЛИ или XOR. Например, очистка младшего установленного бита с помощью
x &= (x-1))
(См.: Каковы наилучшие последовательности инструкций для генерации векторных констант на лету? Для векторов x86 SIMD: аналогичная проблема, вы можете создать
-1на лету дешево, без загрузки из памяти, и передавать его через различные другие инструкции, такие как сдвиг влево, (SSSE3) абсолютное значение. Но делать это стоит только для коротких последовательностей, иначе просто загружать из памяти или mov-немедленно в целочисленные регистры и
movd xmm0, eax)
Шестнадцатеричный — это просто способ представления чисел в тексте, например, ASCII.Вы можете назвать это форматом сериализации.
0xFD00это просто еще один способ написать
64768(основание 10) или
0b1111110100000000(база 2). Таким образом, вы просто строите число в регистре из сдвигов и увеличения/уменьшения. Предполагая, что ваши битовые сдвиги умножаются/делятся на 2, а не на 10 или 16, это двоичные операции, поэтому это двоичное число. Просто удобно выражать желаемое двоичное число в компактном формате, таком как шестнадцатеричный, но на самом деле вам ни в коем случае не нужен шестнадцатеричный, например, строка цифр ASCII с основанием 16.
Это не «шестнадцатеричное число», когда вы создаете его в регистре, это просто число. Во всяком случае, это двоичный файл.
Предполагая, что сложение возможно с двумя регистрами, а не только с константой, а сдвиг влево просто удаляет биты, сдвинутые из 16-битного слова:
t = ~SMASK // 0xff00
return t + (t << 1)
Альтернативой, если сдвиг возможен на произвольные константы, а не только на 1, является
t = SMASK
t += -1
t += -1
t <<= 8
Инверсия 0xFD00 == 0b00000010 11111111 = 0x02ff
Этого можно добиться с помощью SMASK = 0x00FF * 3 + 2 или просто с помощью SMASK | (1 << 9), если это возможно.
a = smask
b = smask << 1
a = a + b
a++
a++
return ~a