Pull to refresh

Преобразование hex->dec — ищем красивые решения

Reading time 1 min
Views 31K
После обсуждения алгоритмов поиска цифр в строке возникла идея рассмотреть в том же ключе какие-нибудь другие задачи. Подходящей показалась задача преобразования целого числа из 16-ричной системы в десятичную: не очень громоздкая, с по меньшей мере одним очевидным алгоритмом и, может быть, многими неочевидными, и понятная.



Дана строка, содержащая целое неотрицательное число в 16-ричной системе. Число записано цифрами 0..9A..F (буквы — только большие), гарантируется, что символов, не являющихся цифрами, в строке нет. Требуется получить строку, содержащую десятичную запись такого числа. Длина входной строки не превосходит 100000 байт.

Пишите решения на любых языках — самые красивые, самые короткие, самые эффективные… Для решений на машине Тьюринга предлагаю использовать только символы «пробел, 0, 1» (новых не вводить), а цифры входа и выхода записывать четверками битов (разделенные пробелами или нет — на ваше усмотрение). На Brainfuck — входная строка должна вводиться, а выходная — печататься.

UPD. Использовать встроенный или библиотечный BigNum, конечно, хорошо, но как-то не очень интересно. Давайте обходиться без него!

Для затравки — решение на C# (которое нельзя назвать ни красивым, ни коротким, ни эффективным):

        static unsafe string Hex2Dec(string x) {
            int l=x.Length;
            int ll=l+l/4+3;
            sbyte[] m=new sbyte[ll];
            int i=l;
            foreach(char c in x) m[--i]=(sbyte)(c<'A' ? c-'0' : c-'A'+10);
            int lk=ll;
            while(l>0) {
                int k=0,l1=0;
                while(l>0) {
                    k=(k<<4)+m[--l];
                    m[l]=(sbyte)(k/10);
                    if(l1==0 && k>=10) l1=l+1;
                    k%=10;
                }
                m[--lk]=(sbyte)(k+48);
                l=l1;
            }
            string res;
            fixed(sbyte *c=m){ res=new string(c,lk,ll-lk); }
            return res;
        }
Tags:
Hubs:
0
Comments 46
Comments Comments 46

Articles