roboforum.ru

Есть процессор, работающий с 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" и какую использовать "какую-то-быструю-операцию" ?

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

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

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

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

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

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

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

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

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

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

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

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

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

blindman писал(а):Поотрывать бы руки тем кто располагает ноги в чипах произвольным образом Ну неужели трудно додуматься - в процессоре нумеровать по часовой стрелке, в АЦП - против

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

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