Пятничный JS: минус без минуса

    И вновь я приветствую всех в моей традиционной рубрике. Сегодня вы узнаете, что же такого особенного произошло 31 декабря 1969 года, ровно за миллисекунду до полуночи. Точнее, вы узнаете не только лишь это, но только к этому примеру я смог подобрать картинку, а развлекательная статья без картинок — нонсенс.

    image


    В последнее время я немного занимаюсь преподаванием. С целью расширить ученику сознание я задал ему такую задачку:
    Написать функцию sub(a, b), которая будет находить разность чисел a и b. Однако в тексте функции не должно быть символа "-".
    Сейчас для любознательного читателя наступило время отложить чтение статьи и попытатся решить задачу самостоятельно. Поэтому, чтобы он случайно не увидел одно из решений, приведённых ниже, я вставлю картинку со снежинкой, которая не растает, пока часы двенадцать бьют.

    image

    Формулируя задачу, я намекал на один конкретный способ, связанный с темой, которую мы недавно проходили. Но уже после я задумался: а какие способы ещё существуют в этом богатом на неочевидные возможности языке? Результатами нескольких часов размышлений на эту тему я хотел бы с вами поделиться.

    Общие соображения


    Самый простой и безглючный способ сделать вычитание без вычитания — это каким-то образом получить значение «минус единица», а затем написать:

    return a + b * minusOne;
    

    Если получить каким-то образом строку "-", можно элементарно превратить её в минус единицу:

    let minusOne = (minusChar + 1) | 0;
    

    Если мы захотим обойтись без этих маленьких трюков, нас ожидает боль. Доставят нам её, во-первых, специальные значения (Infinity, NaN), во-вторых, возможная потеря точности при менее тривиальных операциях над числами. Но это не значит, что нам не нужно пытаться. Всё, что нас не убивает, нас делает сильней.

    Самое очевидное


    Первый способ, который, по моему разумению, должен прийти в голову новичку — это использование Array#indexOf. Конечно, это не первая подходящая вещь, на которую можно наткнуться, если методично читать Флэнагана по порядку. Однако новичку не нужно читать Флэнагана по порядку, так он быстро утонет в обилии ненужной информации. Array#indexOf удачно сочетает в себе простоту и практическую полезность, потому я склонен полагать это самым очевидным решением.

    function sub(a, b){
        let minusOne = [].indexOf(0);
        return a + b * minusOne;
    }
    

    Метод indexOf, как следует из его названия, возвращает индекс элемента в массиве. Если в массиве такой элемент отсутствует, возвращается специальное значение -1. Очень кстати.

    Битовые операции


    А это первое, что должно было прийти в голову какому-нибудь суровому сишнику. Например, так:

    function sub(a, b){
        let minusOne = ~0;
        return a + b * minusOne;
    }
    

    Тильда в джаваскрипте символизирует побитовое отрицание. Из-за особенностей внутреннего представления отрицательных чисел побитовое отрицание нуля волшебным образом оказывается минус единицей. Кстати говоря, верно и обратное, из-за чего некоторые имеют привычку записывать условие вхождения элемента в массив следующим образом:

    if(~arr.indexOf(elem)){ //...
    

    Сейчас, с появлением Array#includes, этот хак становится менее актуальным.

    Также минус единицу можно получить и более изощрёнными способами. Например, побитовым сдвигом:

    let minusOne = 1 << 31 >> 31;
    

    Math


    А это первое, что должно приходить в голову математику. Методы глобального объекта Math предоставляют множество способов. Например:

    function sub(a, b){
        let minusOne = Math.cos(Math.PI);
        return a + b * minusOne;
    }
    

    Или альтернативные способы:

     let minusOne = Math.log(1/Math.E);
    //или даже так
    minusOne = Math.sign(Number.NEGATIVE_INFINITY);
    

    Кстати, способ с логарифмом даёт возможность вычитать числа «напрямую», без предварительного получения минус единицы:

    function sub(a, b){
        return Math.log( Math.E ** a / Math.E ** b);
    }
    

    Впрочем, о проблемах такого подхода я уже писал в «общих соображениях».

    Строки


    Способов получить строку "-" много. Самый очевидный, пожалуй, этот:

    function sub(a, b){
        let minusChar = String.fromCharCode(45);
        let minusOne = (minusChar + 1) | 0; 
        return a + b * minusOne;
    }
    

    Также можно воспользоваться замечательными возможностями Юникода провались они в ад:

    let minusChar = "\u002d";
    

    Кроме того, этот символ можно вытащить из строки, уже его содержащей. Например, так:

    let minusChar = 0.5.toExponential()[2];
    // 0.5.toExponential() == "5e-1"
    minusChar = (new Date(0)).toISOString()[4].
    //(new Date(0)).toISOString() == "1970-01-01T00:00:00.000Z"
    

    Кстати говоря, если мы получили символ минуса, нам вовсе не обязательно получать минус единицу. Можно сделать следующим образом:

    function sub(a, b){
        let minusChar = "\u002d";
        return eval("(" + a + ")" + minusChar + "(" + b + ")");
    }
    

    За это, конечно, придётся в следующей жизни родиться кольчатым червём, но если вы дочитали эту статью до текущего предложения, очевидно, вам нечего терять.

    Когда приходит год молодой


    И раз уж речь зашла о датах, вот ещё один способ получить минус единицу:

    let minusOne = Date.UTC(1969, 11, 31, 23, 59, 59, 999);
    

    Дело в том, что джаваскриптовые даты «под капотом» содержат т.н. Unix time — количество миллисекунд, прошедших с полуночи первого января 1970 года. Соответственно, тридцать первого декабря 1969 года, в 23:59:59 и 999 миллисекунд это значение равнялось в точности -1.

    Не повторять дома


    Напоследок приведу пару сложных и плохо работающих способов.
    Если оба числа положительны, конечны и первое больше второго, можно воспользоваться делением с остатком.

    function sub(a, b){
        let r = a % b;
        while(r + b < a){
            r += b;
        }
        return r;
    }
    

    Это будет работать за счёт того, что a == a % b + b * n, где n — некоторое целое число. Соответственно, a - b == a % b + b * (n - 1), а значит, прибавляя к остатку b, мы рано или поздно получим искомую величину.

    Если хорошенько подумать, можно избавиться от цикла. Действительно, цикл проходит больше нуля итераций, только если b укладывается в a более одного раза. Этого можно избежать следующим образом:

    function sub(a, b){
        return (a + a) % (a + b);
    }
    

    Однако этот способ по-прежнему некорректно работает с отрицательными числами (из-за того, что с ними очень странно работает оператор "%"), с вычитаемым больше уменьшаемого и со специальными значениями.

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

    function sub(a, b){
        var d = 1; // дельта. то, что мы будем пытаться прибавить к b так, чтобы получилось не более чем a
        var r = 0; // наш будущий результат вычитания
    
    //сначала находим d, превышающее разность.
        while(b + d < a){
            d *= 2;
        }
    //далее последовательно прибавляем его к r, при необходимости уменьшая вдвое
        while(b + r < a){
            if(b + r + d > a){
                d /= 2;
            }else{
                r += d;
            }
        }
    //в силу конечной точности представления чисел в js этот процесс когда-нибудь закончится
        return r;
    }
    

    Опять же, этот способ работает, только если a >= b, и если ни одно из чисел не является бесконечностью или NaN.

    На этом я заканчиваю. Если вам удалось придумать способ, существенно отличающийся от приведённых в статье, обязательно напишите об этом в комментариях. Хорошей вам пятницы!
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 47

      +2
      const sub = (a, b) => a + (Number.MAX_SAFE_INTEGER ^ b) + 1
        0
        Интересно. Но опять же работает не везде. sub(1.1, 3.1) == -1.9
          0
          Не вижу ошибки. В точность, заданную операндами, укладывается.
          З.Ы. Это я с точки зрения математики, не знаток спецификации JS. если ей противоречит тогда да, ошибка.
            0
            С точки зрения математики 1.1 — 3.1 — это строго -2 же.
              0
              Неее… 1.1 — это любое число от 1.05 до 1.149(9)
              Вот если 1.100000…
                +3
                Это вы уже как физик.
        0
        Первая мысль, особенно после строчки 31 декабря 1969 года, это Integer Overflow. В js получить не получилось, в php работает:
        php > echo PHP_INT_MIN + PHP_INT_MAX;
        -1
        
          0
          В JS, по сути, нет интов. Так что не судьба(
            0
            > 4294967295|0
            -1
            > new Int8Array([255])[0];
            -1
              0
              А, точно. Типизированные массивы. Вот это я упустил, да.
          0
          Это все может пригодится на практике? В чем суть этого задания, отучить использовать простые и очевидные решения?
            +2
            Это задание учит следующему:

            1. Знать свой инструмент.
            2. Иметь воображение.
            3. Если однажды возникнет необходимость написать жуткий, но необходимый костыль, иметь интеллектуальную готовность это сделать.

            Разумеется, чтобы третий пункт был плюсом, а не минусом, нужно также научиться не писать костыли, пока это действительно не окажется необходимо.
              0
              А как же KISS? А потом удивляемся откуда берутся простыни текста в методах.
                0
                Всё следует упрощать до тех пор, пока это возможно, но не более того (с)

                Естественный пример, зачем нужно такое вычитание, я придумать, конечно, не могу — задача осознанно искусственная. Можно пофантазировать о том, что JS необходимо запустить в некоторой багнутой среде, где интерпретатор крашится на символе "-". Но вообще случается так, что реальные задачи требуют хаков. И если ты всю жизнь программировал строго по учебнику, столкновение с первой такой задачей похоже по ощущениям на столкновение лица с асфальтом.
                  0

                  Пожалуйста, только не давайте таких задач студентам с их неокрепшей психикой и несформировавшимся понятиями о том, что допустимо в промышленной разработке, а что нет. Опытным разработчикам, которые понимают границы применимости, — пожалуйста, но не студентам. Иначе подобный код всплывёт потом на работе просто потому что "а почему бы нет, работает же, стильно-модно-молодёжно" и будет очень больно.

                    –2
                    Ну, если так рассуждать, студентам и сортировку пузырьком нельзя проходить. а то потом напишут её вместо Array#sort и просадят производительность к чертям.
                      0
                      Вы не поверите! Но я видел код в продакшене, где вместо встроенных сортировок, писали свои:)
                        0
                        Ну так и я как-то раз писал. Array#sort не гарантирует стабильность сортировки, хотя бы по этой причине иногда может понадобиться свой велосипед.
                        +1

                        Нет. Это совсем другое. В сортировке пузырьком нет ничего плохого, это нормальный код, это основы алгоритмизации. А это именно хак, причем вы сами даже затрудняетесь придумать пример, где такое может понадобиться.

                          0
                          Я думаю, студенты затруднятся не меньше моего)
                          Вообще, введение понятия должно сопровождаться как примерами того, что в этом понятие входит, так и примерами того, что в него не входит. Так что для объяснения того, что такое хороший, добротный код, надо иногда и грязные хаки демонстрировать.
                            +1

                            Если это приподнести как пример того, как делать не стоит, то конечно, нет проблем :) Просто нужно чтобы это явно было сказано с самого начала, чтобы понимание формировалось у студентов) Чтобы люди четко и ясно понимали, что так делать нельзя в общем случае) Поверьте, это может быть далеко не очевидно для многих)

                              0
                              Да, согласен, тут мой косяк. В прошлых статьях серии я чаще упомнал, что тот, кто будет так делать в продакшоне, попадёт в ад)
                      0
                      Обфускация :)
                    0
                    Придет потом студент домой и будет изобретать бесконечное количество вариантов, как можно решить задачу, не используя «инструменты из коробки», вместо изучения чего-либо полезного. Потом такой студент выйдет работать и будет придумывать искуственные ситуации, когда надо придумывать подобные решения. Программирование изначально точная наука, в таком ключе, лучше в театральный идти — там воображение разовьют как надо и на практике пригодится.
                      0
                      Да ни разу программирование не точная наука. Теория алгоритмов — да. Программирование — нет. Разница как между физикой и инженерией.
                        0
                        Не хочу с вами спорить, пусть будет так, но здравый смысл должен присутствовать всегда, тем более при обучении кого-либо. А то так можно книку написать с главами вида: складываем два числа не используя "+", умножаем не используя "*", и так далее.
                          +2
                          Организуем обмен данными, не используя глобальное состояние. Программируем, не изменяя объекты. Пишем функции, результат выполнения которых зависит только от их входных данных =) Передёргиваю, конечно, но всё же…
                            0
                            У меня была книга о реализации математической библиотеки типа стандартной JS, плюс неограниченной точности в среде, где максимум что есть сложение, вычитание и битовые операции 16-бит чисел. Ассемблер i8080 если что.
                    +3
                    Написать функцию sub(a, b), которая будет находить разность чисел a и b. Однако в тексте функции не должно быть символа "-".

                    function sub(a, b){
                        return sub_internal(a, b);
                    }
                    
                    function sub_internal(a, b){
                        return a - b;
                    }
                    
                      0
                      Я ждал этого коммента) да, точная формулировка будет «в тексте функции, модуля, содержащего эту функцию, а также всех модулей, используемых этой функцией». Но она уж больно громоздкая.
                      +1
                      let sub = (a, b) => ~(~a + b)

                      Как-то так, для целых должно работать.
                        +2
                        1^0xfffffffe старый добрый xor но нужно посмотреть, разрядность системы х64 или х32
                          0
                          Можно считать инты 32-битными, независимо от системы. Но на самом деле там не инты)
                            0
                            Можно считать инты 32-битными, независимо от системы.
                            Хотя я вот написал и задумался, правда ли это.
                              0
                              Я не увидел в стандарте, какой диапазон у числовых значений. Вполне возможно, что старые версии JS сверху были ограничены 32 бита, а новые или те что только планируют будут ограничены 64 битами ну или другим количеством.
                                +2

                                В стандарте явно сказано, что битовые операции преобразуют аргументы в int32.

                                  0
                                  Спасибо, проглядел.
                            0
                            Как вариант можно циклом вычислять разницу, способ конечно примитивный, но работать будет.
                            let sub = function(a,b){
                                let result = 0;
                                let start = b;
                                let end = a;
                                if (a >= b) {
                                    for (let i = start; i<end; i++) {
                                         result++;
                            	}
                                }
                                else {
                                    for (let i = end; i<start; i++) {
                            	    result--;
                            	}
                                }
                                return result;
                            }
                            
                              +1
                              result--;
                              упс)
                                +4
                                Только сейчас понял в чем косяк решения) Вместо того, чтобы использовать минус использовал сразу два) Пойду поаплодирую себе за решение)
                              +1
                              Вариант попроще:

                              int sub(int a, int b)
                              {
                                  if (a == b) return 0;
                                  if (a > b) return sub(b, a);
                                  var i = 0;
                                  while (a < b)
                                  {
                                      i++;
                                      a++;
                                  }
                                  return i;
                              }


                              Вариант посложнее:
                              int sub(int a, int b)
                              {
                                if (a == b) return 0;
                                if (b == a + 1) return 1;
                                if (a > b) return sub(b, a);
                                int sum = 0;
                                if (a%2 == 1 ^ b%2 == 1) sum = 1;
                                sum += 2 * sub(a, (a +b) / 2);
                                return sum;
                              }
                              


                              Правда, оба варианта возвращают разность по модулю… Пойду подумаю еще.
                                0
                                int sub(int a, int b)
                                {
                                    if (a == b) return 0;
                                    if (b == a + 1) return 1;
                                    if (a > b) return (int)Math.Log10(0.1d) * sub(b, a);
                                    int sum = 0;
                                    if (a % 2 == 1 ^ b % 2 == 1) sum = 1;
                                    sum += 2 * sub(a, (a + b) / 2);
                                    return sum;
                                }


                                Варианты с распарсиванием строки в число с указанием номера символа "-" я счел чересчур читерскими )
                                  0
                                  А впрочем, можно куда проще, и так, чтобы работало не только для целых:

                                  return a + Math.Log10(0.1) * b;


                                  Но так даже скучно )
                                +1

                                В порядке бреда :)


                                String(Number.MIN_SAFE_INTEGER)[0] + 1 | 0 // -1
                                  +1

                                  Ещё чуточку идиотии :)


                                  getComputedStyle(document.body)[0].replace(/\w+/g, '') + 1 | 0 // -1

                                  Очень хочется выцепить "-" как-нибудь через try-catch и поиск символа в тексте ошибки, но что-то никак не могу подобрать подходящую ошибку. Попробовал с регулярками повоевать — тоже пока ничего хитрого не придумал :)

                                    0
                                    Точно. Собирался написать что-нибудь с DOMом, но забыл.
                                  +1

                                  Спасибо. Напомнило измерение высоты здания с помощью барометра.

                                  Only users with full accounts can post comments. Log in, please.