Easyelectronics.ru

Электроника для всех
Текущее время: 23 сен 2019, 05:58

Часовой пояс: UTC + 5 часов



JLCPCB – Прототипы печатных плат за $2/10pcs (Любой цвет!)
Крупнейший производитель печатных плат и прототипов. Более 600000 клиентов и свыше 10000 заказов в день!
Получите скидку на почтовую отправку при первом заказе в JLCPCB!

Начать новую тему Ответить на тему  [ Сообщений: 14 ] 
Автор Сообщение
 Заголовок сообщения: Представление числа в обратном порядке.
СообщениеДобавлено: 05 дек 2014, 14:42 
Старожил

Зарегистрирован: 26 апр 2012, 19:19
Сообщения: 364
Нужен алгоритм как представить число в 4-чной и 8-чной системах счисления в обратном порядке. Задачу решаю на stm32.
Например:
для четверичной системы число 1323012 преобразуется в число 2103231
для восьмеричной системы: 6375021 в число 1205736
У кого какие мысли?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Представление числа в обратном порядке.
СообщениеДобавлено: 05 дек 2014, 14:50 
Супермодератор
Аватара пользователя

Зарегистрирован: 26 янв 2010, 22:19
Сообщения: 6474
Откуда: Из тех... Из бывших...
Хранить и обрабатывать в формате BCD?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Представление числа в обратном порядке.
СообщениеДобавлено: 05 дек 2014, 15:40 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2619
Откуда: Санкт-Петербург
Я плакалЪ.
Вроде давно ж в теме, и такой вопрос (классический - из простого задания, данного учителем классу: вывести цифры числа в обратном порядке)...
Вы не забыли, что при преобразовании числа в строку _почти всегда_ это делается именно с хвоста? Так что если ваше число int - то просто
Код:
unsigned value = ... // число, которое выводим
const unsigned base = 4; // база для преобразования
for(unsigned t = value; t; t /= base) {
  unsigned digit = t % base;
  output(digit); // вывести цифру
}
Ну, естественно, для base=4 или 8 деление заменяется на >>=log2base, а % на &(base-1) (возможно, если base - константа, то компилятор это и сам сделает - не проверял)

Или у вас числа длинные (больше чем C умеет)? Тогда или делать длинную арифметику, или схитрить и пользоваться для выделения цифры её позицией (старшие биты позиции дадут адрес в представлении числа, младшие - какие биты выделять... но тут код разрастётся)

Или я чего-то не понял?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Представление числа в обратном порядке.
СообщениеДобавлено: 05 дек 2014, 17:01 
Старожил

Зарегистрирован: 26 апр 2012, 19:19
Сообщения: 364
нет! нужно из числа получить число в реверсивном порядке, а не последовательно выводить разряды этого числа в обратном порядке.
Пробую алгоритм БПФ для различных оснований сделать: Radix2, Radix4, Radix8.
Для Radix2 уже сделал, там все просто... есть команда RBIT которая выполняет реверс бит числа.
Например: 01011100 -> 00111010, т.е 92 преобразовывается в 58
Для Radix4 это же число в реверсном порядке выглядело бы так: 00 11 01 01 , т.е. 53
Для Radix8 это же число в реверсном порядке выглядело бы так: 100 011 001 , т.е. 281


Последний раз редактировалось wypuk 05 дек 2014, 17:06, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Представление числа в обратном порядке.
СообщениеДобавлено: 05 дек 2014, 17:06 
Старожил
Аватара пользователя

Зарегистрирован: 14 апр 2014, 11:06
Сообщения: 1539
Откуда: Курск
1 разложить число на разряды согласно разрядности системы исчисления (простите за тавтологию)
2 перевести в строку
3 перевернуть строку
4 умножить каждый новый разряд на вес этого разряда
5 сумма всех произведений = искомое число


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Представление числа в обратном порядке.
СообщениеДобавлено: 05 дек 2014, 17:30 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2619
Откуда: Санкт-Петербург
wypuk, прошу прощения за неверное предположение.

А сколько разрядов в числе? Немного, я так понимаю?
Может, выгоднее всего табличка?

Ну или вариант: разворачиваете всё число одной командой, раз уж такое есть, а потом AND'ом и сдвигами меняете биты единиц, двоек и четвёрок каждой цифры местами. Примерно так (количество разрядов только поправить):
Код:
y = RBIT(x)>>1; // Упс! Тут поправка - >>1 - чтобы развернуть 5 цифр, а не 5⅓
y1 = y & 011111111;
y2 = y & 022222222;
y4 = y & 044444444;
z = (y1<<2) | y2 | (y4>>2);

Код:
y = RBIT(x);
y1 = y & 0x5555;
y2 = y & 0xAAAA;
z = (y1<<1) | (y2>>1);

А вообще вам, как я понимаю, надо эти числа получать все подряд по порядку - наверное, есть и алгоритм побыстрее.


Последний раз редактировалось aamonster 05 дек 2014, 20:03, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Представление числа в обратном порядке.
СообщениеДобавлено: 05 дек 2014, 18:31 
Старожил

Зарегистрирован: 26 апр 2012, 19:19
Сообщения: 364
В числе максимум 12 разрядов.
Что-то я не понял, как поменять биты каждой цифры местами? можно немного яснее
т.е. сначала инвертировали число полностью, а потом переставляем биты в парах?
Код:
01 11 00 01    RBIT -> 10 00 11 10
                       01 00 11 01


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Представление числа в обратном порядке.
СообщениеДобавлено: 05 дек 2014, 18:49 
Старожил
Аватара пользователя

Зарегистрирован: 17 апр 2010, 08:38
Сообщения: 4913
Откуда: Усинск, республика Коми
Делать сдвиг влево через бит четности, который помещать в новое число опять же сдвигом, только левым. Ну или наоборот, кому как нравится.

_________________
хаос это непознанный порядок


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Представление числа в обратном порядке.
СообщениеДобавлено: 05 дек 2014, 19:24 
Старожил

Зарегистрирован: 15 янв 2013, 13:24
Сообщения: 5665
@BigLeha:
не бит четности, а бит переноса


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Представление числа в обратном порядке.
СообщениеДобавлено: 05 дек 2014, 19:59 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2619
Откуда: Санкт-Петербург
wypuk, угу. Я пример кода для троек и пар битов написал. Раз есть RBIT - такой подход всяко быстрее разворотов через бит переноса.
Ну или можно для 12 бит (т.е. 4 8-ричные цифры или 6 4-ричных) всё сделать через and - сдвиг - or, аналогично классическому алгоритму для bit reverse:

Классика:
Код:
unsigned int reverse(register unsigned int x) {
    x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
    x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
    x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
    x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
    return((x >> 16) | (x << 16));
}

Урезаем до 16 бит, меняем 4-ичные цифры:
Код:
unsigned int reverse4_16(register unsigned int x) {
    x = (((x & 0xcccc) >> 2) | ((x & 0x3333) << 2)); // меняем местами биты 15-14 и 13-12, 11-10 и 9-8, 7-6 и 5-4, 3-2 и 0-1
    x = (((x & 0xf0f0) >> 4) | ((x & 0x0f0f) << 4)); // меняем 15-12 и 11-8, 7-4 и 3-0
    return((x >> 8) | ((x & 0xff) << 8)); // меняем 15-8 и 7-0
}
(ушла строка, меняющая местами чётные и нечётные биты, маски укоротились, ушла строка, меняющая 31-16 и 15-0)

Для 8-ричных цифр можно расписать аналогично (только маски выписывать удобнее 8-ричные, на 12 бит 4 разряда - будет всего 2 строки, а не 3), будет платформенно-независимый (но достаточно быстрый) код. Но с RBIT быстрее (UPD: я там поправил код для восьмиричных цифр).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Представление числа в обратном порядке.
СообщениеДобавлено: 05 дек 2014, 21:01 
Старожил

Зарегистрирован: 26 апр 2012, 19:19
Сообщения: 364
Цитата:
aamonster

Все, я разобрался в твоей идее: делаем инверсию числа -> выделяем четные и нечетные биты по отдельности -> для четных - сдвиг влево, для нечетных - сдвиг вправо -> склеиваем два числа. Все ясно! Аналогично и для троек бит. Итого для Radix4 - 6 тактов для вычисления инверсного индекса. Неплохо!
А приведенный тобой классический алгоритм откуда взят? Так, чисто для общего развития хотелось бы описание почитать.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Представление числа в обратном порядке.
СообщениеДобавлено: 06 дек 2014, 01:42 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2619
Откуда: Санкт-Петербург
Ну я его просто по словам bit reverse нагуглил, т.к. помнил, что он есть. Принцип такой же простой: вначале меняем местами чётные и нечётные биты (and с маской для выделения нужных, shift, потом or для объединения чётных и нечётных), потом чётные и нечётные пары бит, потом группы по 4, по 8 и по 16.
Люди бенчмарк делали, чтобы выбрать лучший алгоритм bitreverse. LUT на первом месте, конечно, но и такой неплох.

А есть и вообще малопонятные алгоритмы с умножением...

https://graphics.stanford.edu/~seander/ ... rseObvious - несколько основных методов и другие битовые хаки.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Представление числа в обратном порядке.
СообщениеДобавлено: 06 дек 2014, 11:00 
Старожил

Зарегистрирован: 26 апр 2012, 19:19
Сообщения: 364
LUT - это табличный метод?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Представление числа в обратном порядке.
СообщениеДобавлено: 06 дек 2014, 11:25 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2619
Откуда: Санкт-Петербург
Ага, Look-Up Table.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Часовой пояс: UTC + 5 часов


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

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


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB