Как быстрее всего проверить, делится ли данное число на 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: см. это, это доказывает, что это решение ( в некоторых компиляторах) работает быстрее, чем module.

EDIT: Вот объяснение и обобщение.

Обязательный ответ для других учащихся, которые могут прийти в поисках ответа.

if (number % n == 0)

В большинстве случаев вы всегда можете это сделать, доверившись умным современным компиляторам.

Это не означает, что вы разочаровываетесь в изучении веселых способов. Проверьте эти ссылки.

Быстрые тесты на делимость (на 2,3,4,5,. ., 16)?

Небольшие хитрости

Просто используйте i % 15 == 0

1. Поскольку компилятор может легко увидеть, что 15 никогда не изменится, он может свободно выполнять любую оптимизацию операции мода. Это работа авторов компиляторов, чтобы сделать такую ​​​​оптимизацию, если они не придумали лучший способ сделать это, вы не будете.

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

3. Еще одна вещь, которую следует учитывать, это то, что ваш компилятор был написан для системы, на которой он находится, ваш код с другой стороны везде одинаков, если вы пишете какой-то странный код, который может быть таким же быстрым на одной системе (вероятно, все же не быстрее ), но на другой системе со специальной аппаратной оптимизацией ваш код может проигрывать на порядок. Поскольку вы написали какой-то эзотерический код для проверки делимости, компилятор вряд ли поймет, что он может оптимизироваться для одной аппаратной операции, написание очевидных вещей сделает вашу жизнь лучше и облегчит компилятору.

4. Поскольку вы на самом деле не проверили, что скорость имеет значение при написании кода, странный способ сделает код очень трудным для чтения для следующего человека и более подверженным ошибкам ( преждевременная оптимизация — корень всех зол)

5. Он по-прежнему работает независимо от того, являются ли входные данные 16-, 32- или 64-битными, поскольку он не зависит от манипуляций с битами.

6. Даже если автор компилятора не реализовал его, очевидно, что кто-то может его реализовать (даже вы сами)

В достаточно современном процессе деление на 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 — это основание, используемое для представления числа. (Для меньших множителей последняя цифра должна делиться на множитель).

Однако не ожидайте, что это будет быстро в коде.