roboforum.ru

Технический форум по робототехнике.

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

Вопросы не попавшие в другие категории.

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

Сообщение blindman » 18 мар 2010, 07:25

Есть процессор, работающий с 16-разрядными двоичными числами без знака. Операция R(x) меняет порядок следования битов в числе x на обратный: R(10000000000000002) = 00000000000000012, R(10100000000000002) = 00000000000001012, R(01010000000000012) = 10000000000010102, и т.д. Очевидно, что 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" и какую использовать "какую-то-быструю-операцию" ? :D
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

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

Сообщение blindman » 18 мар 2010, 08:13

Задачу я решил, если кому интересно - подумайте, предлагайте варианты. Потом я свой напишу
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

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

Сообщение blindman » 18 мар 2010, 08:15

Опа... поторопился... похоже мое решение неверное
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

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

Сообщение =DeaD= » 18 мар 2010, 08:18

Сравнить то в каком смысле? :) хоть не "!=" ? я так понимаю нужна операция "<"?
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

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

Сообщение Michael_K » 18 мар 2010, 08:19

задача какая-то... некорректная, имхо.
во-первых, непонятно, что значит "сравнить",
во-вторых, "придумать какую-то быструю операцию" - это что?
Ну вот классная операция:
"сравнить, поделить, и подпрыгнуть" - исполняется за одну шестую такта.
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

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

Сообщение blindman » 18 мар 2010, 08:20

меньше/больше или равно
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

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

Сообщение blindman » 18 мар 2010, 08:22

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

операция, которая выполнится за 1 команду процессора. Конкретнее - Parallax Propeller.
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

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

Сообщение blindman » 18 мар 2010, 08:24

Казнить нельзя помиловать :)
Сравнить - значит определить "меньше" или "больше или равно"
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

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

Сообщение Michael_K » 18 мар 2010, 08:30

Если задача практическая, то может быть проще анроллить первый цикл по два действия скажем,
не сэкономите на "выдуманной операции", зато сэкономите на цикле... :pardon: :oops:
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

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

Сообщение blindman » 18 мар 2010, 08:34

Количество итераций неопределено, важно минимальное время выполнения итерации цикла (интервал между сравнениями)
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

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

Сообщение Michael_K » 18 мар 2010, 08:41

не... два такта в один упихать... наверное не получится :pardon:
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

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

Сообщение =DeaD= » 18 мар 2010, 08:59

Решения нет, очевидно результат искомой операции зависит сначала от младшего бита (x), потом от второго и т.п.
Очевидно такой атомарной операции случайно подходящей быть не может. Хотя конечно система команд Propeller'а мне незнакома :)
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

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

Сообщение blindman » 18 мар 2010, 09:41

Поотрывать бы руки тем кто располагает ноги в чипах произвольным образом :x Ну неужели трудно додуматься - в процессоре нумеровать по часовой стрелке, в АЦП - против
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

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

Сообщение Michael_K » 18 мар 2010, 10:11

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

:) А вы их на разные стороны платы ставьте...
Вообще, посыл странный :pardon:
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

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

Сообщение =DeaD= » 18 мар 2010, 10:22

Разные стороны платы - это двухсторонний монтаж в дальнейшем, а это лишние деньги и гемор.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

След.

Вернуться в Обо всём

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

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 0

cron