Подразделение в процессоре занимает много времени, поэтому я хочу спросить, как проверить быстрый способ, если число делится на какое-то другое число, в моем случае мне нужно проверить, является ли число делимым на 15.
Кроме того, я просматривал веб-страницы и нашел интересные способы проверить, не является ли число из числа, но я ищу быстрый вариант.
ПРИМЕЧАНИЕ:, поскольку разделение занимает много времени, я ищу ответ без / и %.
Умножение занимает меньше времени, чем деление, поэтому вы можете попробовать следующее:
inline bool divisible15(unsigned int x)
{
//286331153 = (2^32 - 1) / 15
//4008636143 = (2^32) - 286331153
return x * 4008636143u <= 286331153u;
}
Этот способ работает, потому что 2^32-1 (максимальное 32-битное значение) делится на 15, однако если вы возьмете, например, 7, это будет выглядеть как работа, но не будет работать во всех случаях.
EDIT: Смотрите this, это доказывает, что это решение (для некоторых компиляторов) быстрее, чем модуль.
Обязательный ответ для других учащихся, которые могут найти ответ.
if (number % n == 0)
В большинстве случаев вы всегда можете это сделать, доверяя компиляторам smart modern.
Это не значит, что вам не рекомендуется изучать забавные способы. Проверьте эти ссылки.
Просто используйте i % 15 == 0
Так как компилятор может легко видеть, что 15 никогда не изменится, он может свободно делать любую оптимизацию, которую он хочет в операции мод. Это работа писателей-компиляторов, чтобы сделать такую оптимизацию, если они не думали о лучшем способе сделать это, вы не будете.
Например, очень легко проверить, делится ли число на 2, потому что вы просто проверяете первый бит. Разработчики компилятора знают это, и вы можете написать код самостоятельно, чтобы проверить первый бит, но особенно зрелый компилятор будет думать о людях и работать над этими вещами в течение многих лет. Этот тип оптимизации очень простой, поскольку требуется только изменение инструкции или 2, оптимизации, такие как лучшее распределение регистров, намного сложнее достичь.
Еще одна вещь, которую следует учитывать, заключается в том, что ваш компилятор был написан для системы, в которой он включен, с другой стороны, код, с другой стороны, везде одинаковый, если вы пишете какой-то странный код, который может быть столь же быстрым на одном (возможно, еще не быстрее), но на другой системе, которая имеет специальную аппаратную оптимизацию, ваш код может потерять на порядок. Поскольку вы написали какой-то эзотерический код для проверки делимости, компилятор вряд ли осознает, что он может оптимизировать единую аппаратную часть, написав очевидную вещь, чтобы сделать жизнь лучше для вас и проще для компилятора.
Поскольку вы на самом деле не проверяли, что скорость важна для написания кода, странный способ сделает код очень трудным для чтения для следующего человека и более склонным к ошибкам (преждевременная оптимизация - корень всего зла)
Он по-прежнему работает, является ли вход 16, 32 или 64 бита, поскольку он не полагается на бит-манипуляцию.
Даже если автор компилятора не реализовал его, очевидно, что кто-то может реализовать его (даже самостоятельно)
В разумно современном процессе деление на 15 не должно быть таким страшным. Руководство по оптимизации AMD определяет его на основе частного (значение, которое разделяется), и оно занимает 8 + бит позиции самого значимого бита частного. Поэтому, если ваши номера имеют установленный 63-й бит, вы получаете 71 цикл, что, конечно, довольно длинная инструкция. Но для 32-битного числа с несколькими нулями в верхних битах мы говорим о 30-40 циклах. Если число соответствует 16-битовому значению, мы будем иметь максимум 23 цикла.
Чтобы получить остальную часть, это еще один такт.
Если вы делаете это ВСЕ время, конечно, вы можете обнаружить, что это время довольно длинное, но я не уверен, что существует тривиальный способ избежать этого.
Как и другие, компилятор может заменить его чем-то лучшим. Но 15, по моему мнению, не имеет очевидного быстрого решения (если у вас 16 вместо 15, то мы можем использовать трюк x & 15).
Если это ограниченный диапазон, вы можете построить таблицу [ vector<bool>, например, которая будет хранить 1 бит на запись], но вы довольно скоро столкнетесь с проблемой, что доступ к кешированной памяти происходит так же, как и долгое время как операция деления...
Есть несколько интересных способов выяснить, делит ли число на 3, 5 и т.д., суммируя цифры, но, к сожалению, они работают только на десятичных разрядах, что связано с длинной последовательностью делений.
Здесь другой подход, который, вероятно, медленнее, чем другие, но использует только добавление, побитовое и сдвиг:
int divisible15(unsigned int x) {
if (x==0) return 1;
x = (x & 0x0f0f0f0f) + ((x&0xf0f0f0f0)>>4);
x = (x & 0x00ff00ff) + ((x&0xff00ff00)>>8);
x = (x & 0x0000ffff) + ((x&0xffff0000)>>16);
x = (x & 0x0f) + ((x&0xf0)>>4);
return x==15;
}
Идея состоит в том, что делимость на 15 в базе 16 равна делимости на 9 в базе 10 - сумма цифр должна быть делимой на 15.
Таким образом, код суммирует все шестнадцатеричные цифры (аналогично тому, как вы подсчитываете биты), а сумма должна быть равна 15 (кроме 0).
Хорошо, это очень легко сделать в вашей голове, если у вас есть шестнадцатеричное представление. Просто суммируйте все цифры, пока у вас не будет одной цифры. Если ответ равен "0xf", он делится на 15.
Пример 0x3a98: 3 + 0xa + 9 + 8 = 0x1e = 1 + 0xe = 0xf, так что делится на 15.
Это работает для всех факторов на X-1, где X - база, используемая для представления числа. (Для меньших факторов конечная цифра должна делиться на множитель).
Не ожидайте, что это будет быстро в коде.