Разминка для мозгов: перевод десятичного числа в двоичную систему

Было высказано одно пожелание продолжить рубрику «Разминка для мозгов». Что ж, получайте!

В разделе «Готовые решения» есть программа для перевода десятичного числа в двоичную систему на Pascal.

(1) Задание для новичков: перевести программу с Pascal на С++. Желательно сам перевод числа оформить в виде функции (+1 к скиллу).

(2) Задание для продвинутых новичков: выполнить (1) и оптимизировать алгоритм.

(3) Задание для сильно продвинутых новичков: выполнить (1) и (2) и обобщить алгоритм для всего диапазона значений типа int. Строка результата должна содержать двоичное представление числа без лидирующих нулей (для отрицательных чисел — представление в дополнительном коде).

Примечание. Считать, что пользователь всегда вводит корректное значение (для (1) и (2) это целое положительное значение, больше 0).

PS. Попробуйте решить задачу без подсказок. Это же разминка для мозгов, а не соревнование на лучший запрос поисковой системе ))

Можно использовать битовые операции?

Можно использовать любые стандартные (в пределах C++11, для совместимости) возможности языка.

Раз никто не пишет, то я напишу немного :)

#include <iostream>
#include <string>

template <typename T>
std::string intToBin(T val)
{
    if (val == 0)
        return "0";

    std::string bin;

    bool meetOne = false;

    for (int i = sizeof(T) * 8 - 1; i >= 0; i--)
    {
        if (val & (1 << i))
        {
            meetOne = true;
            bin += '1';
        }
        else
        {
            if (meetOne)
            {
                bin += '0';
            }
        }
    }

    return bin;
}

int main()
{
    int val;
    while (std::cin >> val)
    {
        std::cout << intToBin(val) << std::endl;
    }

    return 0;
}

porshe, отличное решение.

Но возможны и другие варианты...

А существует решение эффективнее? (деление, очевидно не будет эффективнее никогда, так как оно работает за logN а моё за константу)

porshe, можешь сразу добавить свое решение в соответствующий раздел :-)

porshe, решение, представленное здесь, и решение в «готовых решениях» разные. И первое мне нравится гораздо больше. Дело даже не в том, что ты во втором решении возвращаешь ссылку на статическую локальную переменную, хотя такие финты мне тоже как-то не по душе. А в том, что такой код явно непотокобезопасен.

С точки зрения эффективности, мне кажется, что это экономия на спичках. (Я код не таймировал, чисто IMHO.) Хотя...

Если уж очень хочется «поэффективнее», есть два варианта ))

Вариант 1. В твой первый код просто после std::string bin; добавить bin.reserve(sizeof(T) * 8);.

Вариант 2. Отказаться (почти) от std::string:

template <typename T>
std::string intToBin(T val) {
    if (val == 0)
        return "0";  // здесь сработает конструктор std::string

    char bary[sizeof(T) * 8 + 1];
    int idigit = 0;
    bool meetOne = false;

    for (int i = sizeof(T) * 8 - 1; i >= 0; i--) {
        if (val & (1 << i)) {
            meetOne = true;
            bary[idigit++] = '1';
        }
        else {
            if (meetOne) {
                bary[idigit++] = '0';
            }
        }
    }
    bary[idigit] = '\0';

    return bary;  // или здесь сработает конструктор std::string
}

Итого всего один вызов конструктора std::string на один вызов функции. Всё остальное — кондовый С безо всякой подкапотной магии STL.

Было бы интересно проверить какой из четырёх вариантов всё-таки быстрее работает... ;)

Кстати, я что-то там говорил про «возможны и другие варианты». Вот такой, например:

#include <iostream>
#include <string>

using namespace std;

void dec2bin_r(unsigned int num, string & str) {
    if (num != 0) {
        dec2bin_r(num >> 1, str);
        str += (num & 1) + '0';
    }
}

string dec2bin(int num) {
    if (num == 0) {
        return "0";
    }
    else {
        string str;
        dec2bin_r(static_cast<unsigned int>(num), str);
        return str;
    }
}

int main() {
    int val;
    while (std::cin >> val) {
        std::cout << dec2bin(val) << std::endl;
    }
    return 0;
}

Не особо эффективно, зато забавно ))

Вариант 1. В твой первый код просто после std::string bin; добавить bin.reserve(sizeof(T) * 8);.

В моём втором решении (которое в готовых) такое есть :)

во втором решении возвращаешь ссылку на статическую локальную переменную, хотя такие финты мне тоже как-то не по душе

Почему? Я видел много функций, где применяется подобная практика. В том числе из стандартной библиотеки С.

Было бы интересно проверить какой из четырёх вариантов всё-таки быстрее работает... ;)

Результаты проверки на случайных 10 млн. чисел (data.txt, генерировался один раз):
1 выполнение — мой первый вариант
2 выполнение — мой второй вариант (из готовых решений)
3 выполнение — ваш вариант с отказом (почти) от std::string
4 выполнение — ваш вариант с рекурсией

porshe, то, что во втором решении такое есть, я видел )) и посоветовал его же использовать и в первом решении.

Почему? Я видел много функций, где применяется подобная практика. В том числе из стандартной библиотеки С.

Хреновая практика. Кстати, стандартная библиотека C — не всегда лучший пример для подражания. Посмотри в документации сколько там функций признаны небезопасными. А gets() даже из стандарта исключили. Всё хорошо в своём контексте. Со времени разработки С и его стандартной библиотеки контекст сильно поменялся.

Один ответ на твоё «почему» я уже дал: версия функции из «готовых решений» нереентерабельна. Т.е. в многопоточном приложении при почти одновременном обращении к этой функции из разных потоков будет большая бяка.

Ещё одна демонстрация несколько искусственна, но вполне возможна:

#include <iostream>
#include <string>

using namespace std;

template <typename T>
const std::string& intToBin(T val) {
    // код функции из "готовых решений" покоцан для краткости
}

int main() {
    int num1 = 1, num2 = -1;
    const string &str1 = intToBin(num1);
    const string &str2 = intToBin(num2);

    cout << num1 << " -> " << str1 << endl;  // упс!
    cout << num2 << " -> " << str2 << endl;

    return 0;
}

Выводы по результатам проверки на скорострельность

Я в общем-то предполагал, что сведение к минимуму использования STL увеличит скорость работы.

Более чем полуторакратный разрыв между 1 и 2 — это время работы конструктора пустой строки и время работы конструктора копирования при возврате строки из функции против времени работы вызовов bin.clear(); bin.reserve(sizeof(T) * 8);.

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

Трудно сказать. Может зависеть и от реализации библиотек, и от оси, возможно, и от компилятора, и от ключей компиляции. Попробуй посмотреть под профайлером. Кстати, для Debug и Release результаты могут быть разные.

Примитивное таймирование показало результат (номер варианта -> время в секундах):

Debug

1 -> 222.938
2 -> 198.49
3 -> 60.812
4 -> 226.559

Release

1 -> 2.87
2 -> 2.843
3 -> 2.027
4 -> 1.954

MS Visual Studio Community 2015

Кстати, в вакууме рекурсивный алгоритм (4) работает быстрее, чем твой итерационный алгоритм (1 или 2). Поскольку он не обрабатывает старшие незначащие нули в битовом представлении числа. А твой алгоритм всегда «сканирует» все биты.

Примитивное таймирование показало результат...

По результатам таймирования предлагаю сменить решение в соответствующем разделе.

Версия кода, которая сейчас опубликована в «готовых решениях» — не лучший вариант.

Вопрос в том, какой вариант из оставшихся лучший. И ещё вопрос: с какой точки зрения выбирать лучший вариант.

С одной стороны, лучше вариант, который в этом обсуждении был опубликован первым: идеологически (С++) он наиболее выдержан.

Вариант с отказом (почти) от std::string по сравнению с ним выглядит хаком, даунгрейдом (почти) до чистого С. Хотя ничего предосудительного в этом нет. И по скорости работы он лучше, чем первый.

Рекурсивный вариант вроде тоже неплох. И идеологически в духе С++. Но с быстродействием вопрос. Видимо зависит от компилятора и оптимизаций. Как правило, рекурсивные алгоритмы всё-таки обычно проигрывают итерационным за счёт накладных расходов на вызов подпрограммы.

Кстати, porshe, ты замеры делал на дебажной или на релизной версии? А с вариантами оптимизации не пробовал поиграть?

Кстати-2, можно попробовать допилить рекурсивный вариант в плане отказа (почти ;) ) от std::string.

Вопрос в том, какой вариант из оставшихся лучший. И ещё вопрос: с какой точки зрения выбирать лучший вариант.

Мне кажется, критерий для выбора лучшего решения — быстродействие.

Кстати, porshe, ты замеры делал на дебажной или на релизной версии? А с вариантами оптимизации не пробовал поиграть?

Замеры делал только для debug версии, и не игрался с оптимизациями. Думаю, так будет очевиднее разница в скорости работы алгоритмов.

Debug-версия, кроме отключенной оптимизации, содержит кой-какой дополнительный код для удобства отладки. Как то: «инициализация» неинициализированных массивов, контроль выхода за границу массива и т.п. Есть подозрение, что при вызове функции там тоже что-то добавляется для контроля использования стека. (Не проверял.) Это я к вопросу о быстродействии. И, в частности, о быстродействии рекурсивной версии.

Проверять надо однако ;)

Ну и по результатам последней проверки поправляй код в «готовых решениях».

PS. Хотя я выбрал бы твой первый вариант, из соображений идеологической правильности и соответствия его генеральной линии партии С++.

Я тоже решил выпустить свою версию проги. Лишь недавно начал погроммировать в C++ (да и си# тоже) и прошу особо тапками не кидаться)

    int main(void)
{
    setlocale(LC_CTYPE, "rus");
    printf("Введите число для обработки\n");
    scanf("%f",&num); numr = num; 
    while(detect != 1) 
    {
               while(detect != 1 || num < 0) 
               {
                          num = num - pow(2,step);
                               if(num < 0){
                                      step--;
                                      num = numr - pow(2,step);
                                      if(num == 0){detect=1;}
                                      break;
                                 }
                          else if(num == 0){ detect=1; break;}
                          else {step++; num = numr;}           
               }
               bin = bin + pow(10,step);
               numr = num; step = 0;
    }
    printf("Вот ваше число в двоичном коде: %f\n", bin);
    scanf("%f",num);
    return 0;
}

Проверять надо однако ;)

Сделал проверку для всех вариантов вот таким скриптом run.sh

#!/bin/bash

echo "Уровень оптимизации - 0, уровень отладочной информации - 0"
g++ $1 -g0 -O0
time ./a.out < data.txt > /dev/null

echo "Уровень оптимизации - 0, уровень отладочной информации - 3"
g++ $1 -g3 -O0
time ./a.out < data.txt > /dev/null

echo "Уровень оптимизации - 3, уровень отладочной информации - 0"
g++ $1 -g0 -O3
time ./a.out < data.txt > /dev/null

echo "Уровень оптимизации - 3, уровень отладочной информации - 3"
g++ $1 -g3 -O3
time ./a.out < data.txt > /dev/null

Результаты:

UPD

Ну и по результатам последней проверки поправляй код в «готовых решениях».

Изменил код в готовых решениях. Таки выбрал по быстродействию, так как считаю, что в данном разделе должны публиковаться лучшие (из возможных) решения. Обычных решений в интернете и так много.