Как я могу изменить mod с побитовым И [дублированием]
Используйте lodash.sortBy , (инструкции с использованием commonjs, вы также можете просто поместить [tag] тег include-tag для cdn вверху вашего html)
var sortBy = require('lodash.sortby');
// or
sortBy = require('lodash').sortBy;
По убыванию
var descendingOrder = sortBy( homes, 'price' ).reverse();
По возрастанию
var ascendingOrder = sortBy( homes, 'price' );
6 ответов
Вот что делает компилятор Microsoft при компиляции разделов небольшими интегральными константами. Предположим, что 32-разрядная машина (код может быть соответствующим образом скорректирован):
int32_t div10(int32_t dividend)
{
int64_t invDivisor = 0x1999999A;
return (int32_t) ((invDivisor * dividend) >> 32);
}
. Что здесь происходит, мы умножаемся на близкое приближение 1/10 * 2 ^ 32 и затем удаляем 2 ^ 32. Этот подход может быть адаптирован к различным делителям и различным битовым ширинам.
Это отлично подходит для архитектуры ia32, так как его команда IMUL поместит 64-разрядный продукт в edx: eax, а значение edx будет требуемое значение. Viz (при условии, что дивиденд передается в eax, а фактор возвращается в eax)
div10 proc
mov edx,1999999Ah ; load 1/10 * 2^32
imul eax ; edx:eax = dividend / 10 * 2 ^32
mov eax,edx ; eax = dividend / 10
ret
endp
Даже на машине с инструкцией с медленным умножением это будет быстрее, чем различие в программном обеспечении.
Конечно, вы можете, если можете жить с некоторой потерей точности. Если вы знаете диапазон значений ваших входных значений, вы можете получить бит-сдвиг и точное умножение. Некоторые примеры того, как вы можете разделить на 10, 60, ... как описано в этом блоге, чтобы форматировать время самым быстрым способом .
temp = (ms * 205) >> 11; // 205/2048 is nearly the same as /10
Yours, Alois Kraus
-
1Вы должны знать, что промежуточное значение
(ms * 205)может переполняться. – Paul R 5 April 2011 в 22:16 -
2Если вы выполняете int ms = 205 * (i & gt; 11); вы получите неправильные значения, если числа малы. Вам нужен набор тестов, чтобы убедиться, что в заданном диапазоне значений результаты верны. – Alois Kraus 5 April 2011 в 22:28
-
3
-
4
-
5@ernesto & gt; & gt; & gt; 11 - деление на 2048. Если вы хотите разделить на десять, вам нужно разделить это на 2048/10, что составляет 204,8 или 205 в качестве ближайшего целочисленного числа. – Alois Kraus 26 November 2017 в 21:57
Хотя ответы, которые до сих пор соответствуют актуальному вопросу, они не соответствуют названию. Итак, вот решение, сильно вдохновленное Delight Hacker's , которое действительно использует только сдвиги бит.
unsigned divu10(unsigned n) {
unsigned q, r;
q = (n >> 1) + (n >> 2);
q = q + (q >> 4);
q = q + (q >> 8);
q = q + (q >> 16);
q = q >> 3;
r = n - (((q << 2) + q) << 1);
return q + (r > 9);
}
Я думаю, что это лучшее решение для архитектур, которым не хватает команды умножения.
В архитектурах, которые могут сдвигать только одно место за раз, серия явных сравнений с уменьшающимися полномочиями двух, умноженных на 10, может работать лучше, чем решение, получающее удовольствие от хакера. Предполагая 16-битный дивиденд:
uint16_t div10(uint16_t dividend) {
uint16_t quotient = 0;
#define div10_step(n) \
do { if (dividend >= (n*10)) { quotient += n; dividend -= n*10; } } while (0)
div10_step(0x1000);
div10_step(0x0800);
div10_step(0x0400);
div10_step(0x0200);
div10_step(0x0100);
div10_step(0x0080);
div10_step(0x0040);
div10_step(0x0020);
div10_step(0x0010);
div10_step(0x0008);
div10_step(0x0004);
div10_step(0x0002);
div10_step(0x0001);
#undef div10_step
if (dividend >= 5) ++quotient; // round the result (optional)
return quotient;
}
-
1Ваш код выполняет 16 умножений на 10. Почему, по вашему мнению, ваш код быстрее, чем удовольствие от хакера? – chmike 7 October 2017 в 20:11
-
2Неважно, что я думаю. Важно то, работает ли на соответствующей платформе быстрее. Попробуйте сами! Здесь вообще нет самого быстрого решения. Каждое решение имеет определенную платформу и будет лучше работать на этой платформе, возможно, лучше, чем любое другое решение. – Kuba Ober 18 October 2017 в 16:09
-
3Я не заметил, что n * 10 является постоянным. Таким образом, он будет предварительно вычислен компилятором. Я дал альтернативный алгоритм в ответе. Наш алгоритм эквивалентен, за исключением одного различия. Вы вычитаете b * 10 из v, и я добавляю его к x * 10. Вашему алгоритму не нужно отслеживать x * 10, который сохраняет переменную. Код, который вы показываете, разворачивает мой цикл while. – chmike 18 October 2017 в 19:10
-
4@chmike: На машине без аппаратного умножения
n*10все еще дешево:(n<<3) + (n<<1). Эти ответы с малым сдвигом могут быть полезны на машинах с медленным или несуществующим HW-умножением и только сдвигом на 1. В противном случае обратное значение с фиксированной точкой намного лучше для константных делителей времени компиляции (например, современные компиляторы делают дляx/10). – Peter Cordes 18 October 2017 в 21:17
Деление скважины является вычитанием, так что да. Сдвиг вправо на 1 (разделите на 2). Теперь вычитаем 5 из результата, подсчитывая количество вычетов, пока значение будет меньше 5. Результатом будет количество вычитаемых вычетов. О, и деление, вероятно, будет быстрее.
Гибридная стратегия сдвига вправо, а затем деление на 5 с использованием нормального деления может привести к повышению производительности, если логика в делителе еще не делает этого для вас.
4294967219 / 10 = 429496721, но4294967219 * div >> 32 = 429496722. Для более крупных делителей подписанная версия также будет неточной. – Evan 3 July 2017 в 22:12x/10в мультипликативный обратный символ с фиксированной точкой (и делать дополнительный код для обработки отрицательных входов для подписанного деления), чтобы дать правильный ответ для всех возможных 32- бит. Для беззнакового деления на 10 MSVC (и другие компиляторы) ( godbolt.org/g/aAq7jx ) умножаются на0xcccccccdи сдвигают вправо верхнюю половину на 3. – Peter Cordes 18 October 2017 в 21:07