[Задача] Реверсная двоичная арифметика

blindman

Есть процессор, работающий с 16-разрядными двоичными числами без знака. Операция R(x) меняет порядок следования битов в числе x на обратный: R(1000000000000000₂) = 0000000000000001₂, R(1010000000000000₂) = 0000000000000101₂, R(0101000000000001₂) = 1000000000001010₂, и т.д. Очевидно, что R(R(x)) = x.

Дано некое число a. Необходим эффективный алоритм, позволяющий для произвольного x сравнить а с R(x). Сравнение будет выполняться в цикле. Перед входом в цикл можно произвести какие-то преобразования над a, но в теле цикла должен быть минимальный объем вычислений. Процессор позволяет вычислить R(x) за 1 команду. Алгоритм

Код:

цикл
  получить x
  найти R(x)
  сравнить R(x) с a
  использовать-результат-сравнения
конеццикла

считается недостаточно эффективным. Идеальный алгоритм:

Код:

как-то-преобразовать а в b
цикл
  получить x
  выполнить какую-то-быструю-операцию(x,b) <--- CMP, AND, OR, XOR, фиг его знает
  использовать-результат-предыдущей-операции
конеццикла

Собственно задача - придумать как "как-то-преобразовать а в b" и какую использовать "какую-то-быструю-операцию" ?

blindman

Задачу я решил, если кому интересно - подумайте, предлагайте варианты. Потом я свой напишу

blindman

Опа... поторопился... похоже мое решение неверное

=DeaD=

Сравнить то в каком смысле?

хоть не "!=" ? я так понимаю нужна операция "<"?

Michael_K

задача какая-то... некорректная, имхо.
во-первых, непонятно, что значит "сравнить",
во-вторых, "придумать какую-то быструю операцию" - это что?
Ну вот классная операция:
"сравнить, поделить, и подпрыгнуть" - исполняется за одну шестую такта.

blindman

меньше/больше или равно

blindman

Michael_K писал(а):

"придумать какую-то быструю операцию" - это что?

операция, которая выполнится за 1 команду процессора. Конкретнее - Parallax Propeller.

blindman

Казнить нельзя помиловать

Сравнить - значит определить "меньше" или "больше или равно"

Michael_K

Если задача практическая, то может быть проще анроллить первый цикл по два действия скажем,
не сэкономите на "выдуманной операции", зато сэкономите на цикле... :pardon:

blindman

Количество итераций неопределено, важно минимальное время выполнения итерации цикла (интервал между сравнениями)

Michael_K

не... два такта в один упихать... наверное не получится :pardon:

=DeaD=

Решения нет, очевидно результат искомой операции зависит сначала от младшего бита (x), потом от второго и т.п.
Очевидно такой атомарной операции случайно подходящей быть не может. Хотя конечно система команд Propeller'а мне незнакома

blindman

Поотрывать бы руки тем кто располагает ноги в чипах произвольным образом

Ну неужели трудно додуматься - в процессоре нумеровать по часовой стрелке, в АЦП - против

Michael_K

blindman писал(а):

Поотрывать бы руки тем кто располагает ноги в чипах произвольным образом

Ну неужели трудно додуматься - в процессоре нумеровать по часовой стрелке, в АЦП - против

А вы их на разные стороны платы ставьте...
Вообще, посыл странный :pardon:

=DeaD=

Разные стороны платы - это двухсторонний монтаж в дальнейшем, а это лишние деньги и гемор.

roboforum.ru

[Задача] Реверсная двоичная арифметика

Кто сейчас на конференции