Сдвиг вправо на одну позицию с помощью операторов АЛУ? - PullRequest
Новая
       46

Сдвиг вправо на одну позицию с помощью операторов АЛУ?

3 голосов
/ 12 октября 2009

Мне было интересно, существует ли эффективный способ выполнить сдвиг вправо для 8-битного двоичного значения, используя только операторы ALU (NOT, OR, AND, XOR, ADD, SUB) 

Example:

input:  00110101
output: 10011010

Мне удалось реализовать сдвиг влево, просто сложив с собой 8-битное двоичное значение, поскольку сдвиг влево эквивалентен умножению на 2. Однако я не могу придумать, как это сделать для сдвига вправо.

Единственный метод, который я до сих пор придумал, - это просто выполнить 7 сдвигов левого ствола. Это единственный способ?

1 Ответ

2 голосов
/ 12 октября 2009

Тривиально видеть, что это невозможно сделать с {AND, OR, XOR, NOT}. Для всех этих операторов outbit [N] зависит только от inbit1 [N] и inbit2 [N] . И добавляет зависимость от inbit1 [N] .. inbit1 [0] и inbit2 [N] .. inbit2 [0]. Однако в вашем случае вам нужна зависимость от inbit [N + 1]. Следовательно, если есть какое-либо решение, оно должно включать SUB.

Однако A - B - это просто A + (-B), что A + ((B XOR 11111111) +1). Следовательно, если было решение с использованием SUB, его можно было бы переписать как решение с использованием ADD и XOR. Как мы показали, этих операторов недостаточно. Следовательно, набор {ADD, OR, XOR, NOT, ADD, SUB} также недостаточен.

...