Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование в широком смысле слова > Алгоритмика

Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения

Ответ
 
Опции темы
Старый 27.12.2011, 10:22   #1
YellowAfterlife
ПроЭктировщик
 
Аватар для YellowAfterlife
 
Регистрация: 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
pax
Unity/C# кодер
 
Аватар для pax
 
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений
(для 5,323 пользователей)
Ответ: base2 » base10(string)

А что ты получишь делением двоичного числа на 10? Тут как обычно возведение двойки в степень и сложение.
__________________
Blitz3d to Unity Wiki
(Offline)
 
Ответить с цитированием
Старый 27.12.2011, 10:46   #3
SBJoker
Злобный Админ
 
Аватар для SBJoker
 
Регистрация: 04.09.2005
Сообщений: 5,926
Написано 3,415 полезных сообщений
(для 9,330 пользователей)
Ответ: base2 » base10(string)

Классическое: "читаем биты справа налево, преобразуем каждую единицу в число по принципу 2^позиция бита. Прибавляем к итоговому числу. И так по всем битам числа." Не подходит?

Для чисел большой размерности надо прикручивать математику больших чисел на строках.
__________________
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
YellowAfterlife (27.12.2011)
Старый 27.12.2011, 11:06   #4
YellowAfterlife
ПроЭктировщик
 
Аватар для YellowAfterlife
 
Регистрация: 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
pax
Unity/C# кодер
 
Аватар для pax
 
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений
(для 5,323 пользователей)
Ответ: base2 » base10(string)

Что-то я совсем не понял... в числе что хранится десятичное число типа 1010011010? зачем на 10 делить то?

Тут надо битовый сдвиг и битовое И с единицей, потом возведение двойки в степень и сложение.
__________________
Blitz3d to Unity Wiki
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
PackegerX (14.10.2012)
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Часовой пояс GMT +4, время: 05:22.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com