• Как решить данную задачу?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Вспомните алгоритм преобразования числа из 10-чной системы в t-ичную - надо делить на t с остатком, пока есть что делить. Остатки - цифры в t-ичной системе счисления (от младших к старшим).

    Так, 323 в десятичной системе, если перевести в 16-ричную будет:
    323 = 16*20+3. Остаток 3, результат 20.
    20 = 16*1+4. Остаток 4, результат 1
    1 = 16*0+1. Остаток 1. результат 0.

    Отсюда получается, что искомое число в 16-ричной системе 143. Проверка 16*16*1+16*4+3 = 256+64+3=323

    Итак, вам надо сделать то же самое, но не в 10-чиной системе, а в k-ичной (ведь переводим не из 10-чной а из k-ичной). Число записано в виде k-ичных цифр в массиве. Это, фактически, длинная арифметика с базой k.

    Для этого надо реализовать деление числа в виде массива цифр на короткое с остатком.
    Это делается со старших разрядов к младшим. Тупо делите каждую цифру с остатком отдельно. Остаток переносите в младший разряд. Последний остаток - это остаток от всего деления. Результаты делений - новые цифры.

    Удобнее хранить цифры от младших к старшим в массиве. Т.е. элемент массива 0 - это единицы. Элемент 1 - это первая степень k. Еще стоит хранить номер последней ненулевой цифры. Смотрите реализацию по ссылке выше.

    Вот пример из условия. Пусть k=666, t=10, число - {2, 179, 113} (в условии цифры от старших к младшим, но мы храним наоборот).

    Делим на 10.

    113/10 = 11 + остаток 3. Переносим 3 в младший разряд (умножив на 666), получаем 3*666+179=2177.
    2177 / 10 = 217 + остаток 7. 7*666+2 = 4664.
    4664 /10 = 466 + остаток 4. Дальше разрядов нет, значит 4 и есть остаток от деления {2, 179, 113} на 10. Результат деления - {466, 217, 11}

    Последний остаток - 4 - это и есть младшая цифра в ответе (он в условии написан - 50241044). Надо продолжать делить результат пока он не окажется 0.

    Повторим для {466, 217, 11}:
    11/10 = 1 + остаток 1. 1*666+217 = 883
    883/10 = 88 + остаток 3. 3*666+446 = 2444
    2444/10 = 244 + остаток 4.
    Опять, последний остаток - это остаток всего деления и следующая цифра в ответе (опять 4).
    Результаты деления - {244, 88, 1}

    И так далее, пока все число не станет 0 (все цифры в массиве 0).
    Ответ написан
  • Как получить битовое представление типа double в C++?

    gbg
    @gbg
    Баянист. Тамада. Услуги.
    Идея в том, что в double 64 бита. Так что если мы воспользуемся type punning и наложим сверху дабла uint64_t, в котором тоже 64 бита, мы получим 64 битное целое число, содержащее в себе биты исходного дабла.

    *reinterpret_cast(&a)

    Далее, мы используем стандартный трюк с std::bitset для перевода числа в строку, содержащую его двоичное представление

    И потом пара полезных фактов:
    - мы выводим число и его же, но со знаком минус. Можно видеть, что знак хранится в первом бите.
    - аналогично, можем посмотреть, в каких битах хранится экспонента, посмотрев на a, 2*a, 4*a
    #include <iostream>
    #include <bitset>
    using namespace std;
    
    void printBits(const double a)
    {
    	cout << bitset<64>(*reinterpret_cast<const uint64_t*>(&a)) << endl;
    }
    
    int main() 
    {
        const double a = 3.14;
        printBits(a);
        printBits(-a);
        printBits(a*2);
        printBits(a*4);
        return 0;
    }
    0100000000001001000111101011100001010001111010111000010100011111
    1100000000001001000111101011100001010001111010111000010100011111
    0100000000011001000111101011100001010001111010111000010100011111
    0100000000101001000111101011100001010001111010111000010100011111

    Ideone
    Ответ написан