|
Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения |
27.12.2011, 10:22
|
#1
|
ПроЭктировщик
Регистрация: 19.02.2011
Сообщений: 134
Написано 81 полезных сообщений (для 219 пользователей)
|
base2 » base10(string)
На днях столкнулся с проблемой преобразования двоичного числа в десятичную строку (для вывода на экран). Казалось бы, в большинстве языков программирования есть функции преобразования этого рода, но не в этом случае: - Само число представлено как массив беззнаковых 32-битных целочисленных (unit32[]).
- Длина числа может быть разная, от нескольких бит и до бесконечности (точнее, размера ОП). То есть преобразовывать его в int\double не вариант для более чем 32
Что есть: - Числа представлены как экземпляры класса. Класс содержит поля отвечающие за фактическую длину числа в битах "len", количество 32-битных секторов "sectors", сами числа "d[]", и and-маску накладываемую на последний сектор для симуляции "неполного сектора".
- Базовые операции (+, -, and, or, xor, обычные и циклические сдвиги) применяемые к упомянутым выше классам и возможность вырывать\вставлять "куски" любого количества бит\смещения.
- Относительно оптимизированные операции сравнения таких чисел (==, !=, <, <=, >, >=).
- Существующие операции преобразования стандартных 32-битных целочисленных.
Мои идеи в этом отношении: - Реализовать деление на 10 с вычислением остатка на существующих операциях для получения десятичных цифр, преобразовать их в строку.
Преимущества:- Скорее всего это будет работать.
Недостатки:- Необходимость реализации быстрого "битового" деления чисел.
- Вероятно драматически падающая производительность с увеличением длины числа.
Что хотелось бы услышать: какие-либо идеи (не обязательно с каким-либо кодом) того как это сделать более удачно\быстро.
Хорошего дня.
__________________
Мой сайт-блог. Игры, обновления, примеры для Haxe, JavaScript(+HTML5), GameMaker, Love2d...
|
(Offline)
|
|
27.12.2011, 10:41
|
#2
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: base2 » base10(string)
А что ты получишь делением двоичного числа на 10? Тут как обычно возведение двойки в степень и сложение.
|
(Offline)
|
|
27.12.2011, 10:46
|
#3
|
Злобный Админ
Регистрация: 04.09.2005
Сообщений: 5,926
Написано 3,415 полезных сообщений (для 9,330 пользователей)
|
Ответ: base2 » base10(string)
Классическое: "читаем биты справа налево, преобразуем каждую единицу в число по принципу 2^позиция бита. Прибавляем к итоговому числу. И так по всем битам числа." Не подходит?
Для чисел большой размерности надо прикручивать математику больших чисел на строках.
__________________
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
27.12.2011, 11:06
|
#4
|
ПроЭктировщик
Регистрация: 19.02.2011
Сообщений: 134
Написано 81 полезных сообщений (для 219 пользователей)
|
Ответ: base2 » base10(string)
Как я упомянул, преобразовать нужно не в двоичное число, а из двоичного. Результат хранится исключительно как строка для вывода на экран.
Сообщение от pax
А что ты получишь делением двоичного числа на 10? Тут как обычно возведение двойки в степень и сложение.
|
Принцип, в кратце (псевдокод):
function toString(number) {
result = ""; // результат
while (number != 0) {
digit = number % 10; // цифра в конце числа
result = chr(ord("0") + digit) + result; // записываем ее в результат
number = number / 10; // переходим к следующей цифре
}
return result;
}
Суть в том что деление\модуль должны будут быть реализованы отдельно.
Сообщение от SBJoker
Классическое: "читаем биты справа налево, преобразуем каждую единицу в число по принципу 2^позиция бита. Прибавляем к итоговому числу. И так по всем битам числа." Не подходит?
Для чисел большой размерности надо прикручивать математику больших чисел на строках.
|
Подходит (и легко реализуется) для числа влезающего в стандартный формат, т.е. 32 бита, или немного больше для double (не могу сказать наверняка разрядность мантисы).
Строковая математика - неплохой вариант, хотя мне кажется что она будет работать по скорости не очень быстро. Думаю это можно немного исправить таблицей констант (2^n), но нужное количество итераций не очень радует.
__________________
Мой сайт-блог. Игры, обновления, примеры для Haxe, JavaScript(+HTML5), GameMaker, Love2d...
|
(Offline)
|
|
27.12.2011, 11:50
|
#5
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: base2 » base10(string)
Что-то я совсем не понял... в числе что хранится десятичное число типа 1010011010? зачем на 10 делить то?
Тут надо битовый сдвиг и битовое И с единицей, потом возведение двойки в степень и сложение.
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 20:46.
|