Путевской Виктор (vipernn) wrote,
Путевской Виктор
vipernn

Магия

Когда-то давно мне понадобился код (функция) для преобразования строки в целое число. Входящая строка имела вид
[s]dddd,
где
    s    - знак числа (+ или -), опционально;
    dddd - одна или больше цифр от 0 до 9.

Какие-либо иные символы в исходной строке считаются недопустимыми, лидирующие и замыкающие пробелы удаляются до передачи в функцию. То есть, переданная в функцию, строка должна была содержать только число. Стандартные функции (stoi и её аналоги) мне не подходили, поскольку были чрезмерно универсальными и громоздкими. После нескольких попыток решения задачи в лоб, у меня получился довольно таки простой и, самое главное, быстрый код:

int stoi1(const string& src) { const int minus = '-' - '0'; const int plus = '+' - '0'; bool incorrect = true; int res = 0; int sign = 1; int first = 1; for(const char& c: src) { int d = c - '0'; if ((uint)d < 10) { res = res * 10 + d; incorrect = false; } else sign = (d == minus ? -1: (d == plus ? 1: 0)) * first; first = 0; } if (incorrect || (sign == 0)) throw invalid_argument("src"); return sign * res; }

В коде присутствует пара хитрушек, требующих пояснения. Итак, по очереди берем каждый символ строки и, вычитая из него '0', получаем либо цифру, либо что-то иное. Если полученное значение мы преобразуем в целое без знака, то все то, что больше 9 цифрами не является. Цифру добавляем к числу, а нецифру сравниваем с '-' или '+'. Для первого символа (если это нецифра), когда значение first == 1, устанавливаем знак числа (1 или -1). Если нецифра будет встречена позже, то поскольку к этому времени first == 0, то знак числа будет установлен нулевым и это будет сигналом об ошибке. Если после прохода строки, значение переменной incorrect остается true, то значит ни одной цифры из строки мы не получили и, следовательно, исходная строка некорректна.
Код был действительно хорош, но, как оказалось, нет пределов совершенству. В некий момент времени я обратил внимание на значения, определяемых в самом начале констант minus и plus. После этого я внес пару изменений в код, и он стал выглядеть просто таки магическим:

int stoi2(const string& src) { bool incorrect = true; int res = 0; int sign = -5; int first = 1; for(const char& c: src) { int d = c - '0'; if ((uint)d < 10) { res = res * 10 + d; incorrect = false; } else sign = d * first; first = 0; } if (incorrect || (sign != -3 && sign != -5)) throw invalid_argument("src"); return (-4 - sign) * res; }

Код похож на предыдущий, но стал более компактным, и в нем нет прямого сравнения нецифры со знаком числа. Зато есть пара интересных преобразований. Как видно из кода, переменная sign инициализируется значением -5. Далее, при установке знака числа, переменной sign просто присваивается значение нецифры без каких-либо дополнительных сравнений. После завершения цикла, как и в предыдущей версии, проверяем наличие хотя бы одной цифры в числе, а затем сравниваем значение знака числа с магическими (на первый взгляд) числами -3 и -5. Если знак равен какому-либо другому число, то выбрасываем исключение. В ином случае успешно завершаем функцию. Еще одно магическое действие проводится при возвращении значения полученного числа. Знак числа вычитается из еще одного магического числа -4.
В чем же дело? В принципе, истину легко установить при помощи приложений CharMap и Calc. Но мы раскроем сию тайну здесь и сейчас. Устроим, так сказать сеанс, черной магии с последующим разоблачением.
Итак. Если c == '+', то d = '+' - '0' = -5. Если c == '-', то d = '-' - '0' = -3. Теперь видно, что все значения sign, за исключением -3 и -5 являются некорректными. Ну и вишенкой на торте является операция вычитания переменной sign из числа -4. Действительно, если sign == -3, то -4 - (-3) = -1, а если sign == -5, то -4 - (-5) = 1. Вот и вся магия. Также становится понятным инициализация значением -5 переменной sign. Если перед числом вовсе нет знака, то оно остается положительным. Вот так. Простая математика (даже арифметика) и никакого обмана.

Tags: интересное, математика, программирование
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments