В последнее время я немного занимаюсь преподаванием. С целью расширить ученику сознание я задал ему такую задачку:
Написать функцию sub(a, b), которая будет находить разность чисел a и b. Однако в тексте функции не должно быть символа "-".Сейчас для любознательного читателя наступило время отложить чтение статьи и попытатся решить задачу самостоятельно. Поэтому, чтобы он случайно не увидел одно из решений, приведённых ниже, я вставлю картинку со снежинкой, которая не растает, пока часы двенадцать бьют.
Формулируя задачу, я намекал на один конкретный способ, связанный с темой, которую мы недавно проходили. Но уже после я задумался: а какие способы ещё существуют в этом богатом на неочевидные возможности языке? Результатами нескольких часов размышлений на эту тему я хотел бы с вами поделиться.
Общие соображения
Самый простой и безглючный способ сделать вычитание без вычитания — это каким-то образом получить значение «минус единица», а затем написать:
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.
На этом я заканчиваю. Если вам удалось придумать способ, существенно отличающийся от приведённых в статье, обязательно напишите об этом в комментариях. Хорошей вам пятницы!
Комментарии (47)
ZurgInq
30.03.2018 12:37Первая мысль, особенно после строчки 31 декабря 1969 года, это Integer Overflow. В js получить не получилось, в php работает:
php > echo PHP_INT_MIN + PHP_INT_MAX; -1
SlavaRa
30.03.2018 13:52Это все может пригодится на практике? В чем суть этого задания, отучить использовать простые и очевидные решения?
Sirion Автор
30.03.2018 13:56Это задание учит следующему:
1. Знать свой инструмент.
2. Иметь воображение.
3. Если однажды возникнет необходимость написать жуткий, но необходимый костыль, иметь интеллектуальную готовность это сделать.
Разумеется, чтобы третий пункт был плюсом, а не минусом, нужно также научиться не писать костыли, пока это действительно не окажется необходимо.
a1tem
30.03.2018 14:11А как же KISS? А потом удивляемся откуда берутся простыни текста в методах.
Sirion Автор
30.03.2018 14:15Всё следует упрощать до тех пор, пока это возможно, но не более того (с)
Естественный пример, зачем нужно такое вычитание, я придумать, конечно, не могу — задача осознанно искусственная. Можно пофантазировать о том, что JS необходимо запустить в некоторой багнутой среде, где интерпретатор крашится на символе "-". Но вообще случается так, что реальные задачи требуют хаков. И если ты всю жизнь программировал строго по учебнику, столкновение с первой такой задачей похоже по ощущениям на столкновение лица с асфальтом.Evgen52
30.03.2018 15:31Пожалуйста, только не давайте таких задач студентам с их неокрепшей психикой и несформировавшимся понятиями о том, что допустимо в промышленной разработке, а что нет. Опытным разработчикам, которые понимают границы применимости, — пожалуйста, но не студентам. Иначе подобный код всплывёт потом на работе просто потому что "а почему бы нет, работает же, стильно-модно-молодёжно" и будет очень больно.
Sirion Автор
30.03.2018 15:36-1Ну, если так рассуждать, студентам и сортировку пузырьком нельзя проходить. а то потом напишут её вместо Array#sort и просадят производительность к чертям.
Evgen52
30.03.2018 15:48Нет. Это совсем другое. В сортировке пузырьком нет ничего плохого, это нормальный код, это основы алгоритмизации. А это именно хак, причем вы сами даже затрудняетесь придумать пример, где такое может понадобиться.
Sirion Автор
30.03.2018 15:53Я думаю, студенты затруднятся не меньше моего)
Вообще, введение понятия должно сопровождаться как примерами того, что в этом понятие входит, так и примерами того, что в него не входит. Так что для объяснения того, что такое хороший, добротный код, надо иногда и грязные хаки демонстрировать.Evgen52
30.03.2018 16:37+1Если это приподнести как пример того, как делать не стоит, то конечно, нет проблем :) Просто нужно чтобы это явно было сказано с самого начала, чтобы понимание формировалось у студентов) Чтобы люди четко и ясно понимали, что так делать нельзя в общем случае) Поверьте, это может быть далеко не очевидно для многих)
Sirion Автор
30.03.2018 16:51Да, согласен, тут мой косяк. В прошлых статьях серии я чаще упомнал, что тот, кто будет так делать в продакшоне, попадёт в ад)
SlavaRa
30.03.2018 18:16Придет потом студент домой и будет изобретать бесконечное количество вариантов, как можно решить задачу, не используя «инструменты из коробки», вместо изучения чего-либо полезного. Потом такой студент выйдет работать и будет придумывать искуственные ситуации, когда надо придумывать подобные решения. Программирование изначально точная наука, в таком ключе, лучше в театральный идти — там воображение разовьют как надо и на практике пригодится.
Sirion Автор
30.03.2018 18:18Да ни разу программирование не точная наука. Теория алгоритмов — да. Программирование — нет. Разница как между физикой и инженерией.
SlavaRa
30.03.2018 18:22Не хочу с вами спорить, пусть будет так, но здравый смысл должен присутствовать всегда, тем более при обучении кого-либо. А то так можно книку написать с главами вида: складываем два числа не используя "+", умножаем не используя "*", и так далее.
Sirion Автор
30.03.2018 18:27+1Организуем обмен данными, не используя глобальное состояние. Программируем, не изменяя объекты. Пишем функции, результат выполнения которых зависит только от их входных данных =) Передёргиваю, конечно, но всё же…
VolCh
31.03.2018 07:34У меня была книга о реализации математической библиотеки типа стандартной JS, плюс неограниченной точности в среде, где максимум что есть сложение, вычитание и битовые операции 16-бит чисел. Ассемблер i8080 если что.
Evgen52
30.03.2018 14:46Написать функцию sub(a, b), которая будет находить разность чисел a и b. Однако в тексте функции не должно быть символа "-".
function sub(a, b){ return sub_internal(a, b); } function sub_internal(a, b){ return a - b; }Sirion Автор
30.03.2018 15:15Я ждал этого коммента) да, точная формулировка будет «в тексте функции, модуля, содержащего эту функцию, а также всех модулей, используемых этой функцией». Но она уж больно громоздкая.
nikosias
30.03.2018 14:581^0xfffffffe старый добрый xor но нужно посмотреть, разрядность системы х64 или х32
Sirion Автор
30.03.2018 15:16Можно считать инты 32-битными, независимо от системы. Но на самом деле там не инты)
Sirion Автор
30.03.2018 15:23Можно считать инты 32-битными, независимо от системы.
Хотя я вот написал и задумался, правда ли это.nikosias
30.03.2018 15:40Я не увидел в стандарте, какой диапазон у числовых значений. Вполне возможно, что старые версии JS сверху были ограничены 32 бита, а новые или те что только планируют будут ограничены 64 битами ну или другим количеством.
darkdaskin
30.03.2018 16:25В стандарте явно сказано, что битовые операции преобразуют аргументы в int32.
Goodzonchik
30.03.2018 15:15Как вариант можно циклом вычислять разницу, способ конечно примитивный, но работать будет.
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; }Sirion Автор
30.03.2018 15:17result--;
упс)Goodzonchik
30.03.2018 15:22Только сейчас понял в чем косяк решения) Вместо того, чтобы использовать минус использовал сразу два) Пойду поаплодирую себе за решение)
pankraty
30.03.2018 21:28+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; }
Правда, оба варианта возвращают разность по модулю… Пойду подумаю еще.pankraty
30.03.2018 21:41int 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; }
Варианты с распарсиванием строки в число с указанием номера символа "-" я счел чересчур читерскими )pankraty
30.03.2018 23:17А впрочем, можно куда проще, и так, чтобы работало не только для целых:
return a + Math.Log10(0.1) * b;
Но так даже скучно )
faiwer
30.03.2018 22:37В порядке бреда :)
String(Number.MIN_SAFE_INTEGER)[0] + 1 | 0 // -1faiwer
30.03.2018 22:48Ещё чуточку идиотии :)
getComputedStyle(document.body)[0].replace(/\w+/g, '') + 1 | 0 // -1
Очень хочется выцепить "-" как-нибудь через try-catch и поиск символа в тексте ошибки, но что-то никак не могу подобрать подходящую ошибку. Попробовал с регулярками повоевать — тоже пока ничего хитрого не придумал :)
ipanic
const sub = (a, b) => a + (Number.MAX_SAFE_INTEGER ^ b) + 1
Sirion Автор
Интересно. Но опять же работает не везде. sub(1.1, 3.1) == -1.9
dmitryredkin
Не вижу ошибки. В точность, заданную операндами, укладывается.
З.Ы. Это я с точки зрения математики, не знаток спецификации JS. если ей противоречит тогда да, ошибка.
Sirion Автор
С точки зрения математики 1.1 — 3.1 — это строго -2 же.
dmitryredkin
Неее… 1.1 — это любое число от 1.05 до 1.149(9)
Вот если 1.100000…
0xd34df00d
Это вы уже как физик.