forum.boolean.name - base2 » base10(string)

forum.boolean.name (http://forum.boolean.name/index.php)

- Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)

- - base2 » base10(string) (http://forum.boolean.name/showthread.php?t=16108)

base2 » base10(string)

На днях столкнулся с проблемой преобразования двоичного числа в десятичную строку (для вывода на экран). Казалось бы, в большинстве языков программирования есть функции преобразования этого рода, но не в этом случае:

Само число представлено как массив беззнаковых 32-битных целочисленных (unit32[]).
Длина числа может быть разная, от нескольких бит и до бесконечности (точнее, размера ОП). То есть преобразовывать его в int\double не вариант для более чем 32

Что есть:

Числа представлены как экземпляры класса. Класс содержит поля отвечающие за фактическую длину числа в битах "len", количество 32-битных секторов "sectors", сами числа "d[]", и and-маску накладываемую на последний сектор для симуляции "неполного сектора".
Базовые операции (+, -, and, or, xor, обычные и циклические сдвиги) применяемые к упомянутым выше классам и возможность вырывать\вставлять "куски" любого количества бит\смещения.
Относительно оптимизированные операции сравнения таких чисел (==, !=, <, <=, >, >=).
Существующие операции преобразования стандартных 32-битных целочисленных.

Мои идеи в этом отношении:

Реализовать деление на 10 с вычислением остатка на существующих операциях для получения десятичных цифр, преобразовать их в строку.
Преимущества:
- Скорее всего это будет работать.
Недостатки:
- Необходимость реализации быстрого "битового" деления чисел.
- Вероятно драматически падающая производительность с увеличением длины числа.

Что хотелось бы услышать: какие-либо идеи (не обязательно с каким-либо кодом) того как это сделать более удачно\быстро.

Хорошего дня.

Ответ: base2 » base10(string)

А что ты получишь делением двоичного числа на 10? Тут как обычно возведение двойки в степень и сложение.

Ответ: base2 » base10(string)

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

Для чисел большой размерности надо прикручивать математику больших чисел на строках.

Ответ: base2 » base10(string)

Как я упомянул, преобразовать нужно не в двоичное число, а из двоичного. Результат хранится исключительно как строка для вывода на экран.

Цитата:

Сообщение от pax (Сообщение 215380)

А что ты получишь делением двоичного числа на 10? Тут как обычно возведение двойки в степень и сложение.

Принцип, в кратце (псевдокод):

Код:

function toString(number) {

    result = ""; // результат

    while (number != 0) {

        digit = number % 10; // цифра в конце числа

        result = chr(ord("0") + digit) + result; // записываем ее в результат

        number = number / 10; // переходим к следующей цифре

    }

    return result;

}

Суть в том что деление\модуль должны будут быть реализованы отдельно.

Цитата:

Сообщение от SBJoker (Сообщение 215381)

Подходит (и легко реализуется) для числа влезающего в стандартный формат, т.е. 32 бита, или немного больше для double (не могу сказать наверняка разрядность мантисы).
Строковая математика - неплохой вариант, хотя мне кажется что она будет работать по скорости не очень быстро. Думаю это можно немного исправить таблицей констант (2^n), но нужное количество итераций не очень радует.

Ответ: base2 » base10(string)

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

Тут надо битовый сдвиг и битовое И с единицей, потом возведение двойки в степень и сложение.