Как лучше всего в C узнать, делится ли одно число на другое?

Я знаю, что выполнение, то есть 130% 13 приведет к выполнению 130/13 за 10 раз

Балдердаш. % не делает ничего подобного ни на одном из процессоров, которые я когда-либо использовал. Он выполняет 130/13 один раз и возвращает остаток.

Используйте %. Если ваше приложение работает слишком медленно, профилируйте его и исправьте все, что работает слишком медленно.

Для двух произвольных чисел лучший способ проверить, есть ли a % b == 0. Оператор модуля имеет разную производительность в зависимости от оборудования, но ваш компилятор может понять это намного лучше, чем вы. Оператор модуля универсален, и ваш компилятор определит наилучшую последовательность инструкций для любого оборудования, на котором вы работаете.

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

Единственная оптимизация, которая может быть полезной, - это когда делитель равен степени двойки. Затем вы можете использовать &, чтобы замаскировать младшие биты (с помощью делителя - 1) и проверить результат на ноль. Например, чтобы проверить, делится ли a на 8, a & 7 == 0 эквивалентно. Хороший компилятор сделает это за вас, так что придерживайтесь только %.

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

Кроме того, что вы имеете в виду, говоря «делать 130/13 за 10 раз»? Это делает 130 / 13 один раз. Что и требуется.

Если x - константа, тогда да:

if (a * 0x4ec4ec4ec4ec4ec5 < 0x13b13b13b13b13b2) {
    // this will be executed if a is divisible by 13
}

0x4ec4ec4ec4ec4ec5 - это модульное мультипликативное обратное 13 (по модулю 2 ⁶⁴), поэтому, если a действительно кратно 13, тогда произведение будет меньше (2 ⁶⁴ / 13). (Поскольку a в 13 раз больше целого числа n, а n должно соответствовать 64-битному слову, что означает, что оно было меньше 2 ⁶⁴.)

Это работает только для нечетных значений x. Для четных чисел (т. Е. Кратных 2 ^y для y> 0) вы можете объединить этот тест с тестом побитового И (последние y биты a должны быть равны нулю. Если они равны, разделите a на 2 ^y и приступайте к проверке умножения.)

Это имеет смысл только в том случае, если x является константой, потому что вычисление обратного умножения дороже, чем целочисленное деление.

Изменить: я также предполагаю, что a и x беззнаковые.

Когда машина выполняет %, она просто выполняет инструкцию деления, которая автоматически генерирует остаток.

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