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

Question

Какой самый лучший способ, в C, посмотреть, делится ли число на другое?Я использую это:

if (!(a % x)) {
// this will be executed if a is divisible by x
}

Есть ли в любом случае, что быстрее?Я знаю, что выполнение, т.е. 130% 13, приведет к выполнению 130/13 за 10 раз.Таким образом, есть 10 циклов, когда нужен только один (я просто хочу знать, делится ли 130 на 13).

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

Если 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) вы можете объединить этот тест с битовым тестом AND (последние y биты a должны быть равны нулю. Если они равны разделите a на 2 ^y и продолжите тест умножения.)

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

---

Редактировать : Я также предполагаю, что a и x не подписаны.

Answer 5

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

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