Быстро потолок целочисленного деления в C / C++
Учитывая целочисленные значения x и y, C и C++ оба возврата как частное q = x/y этаж эквивалента с плавающей точкой. Я интересуюсь методом возврата потолка вместо этого. Например, ceil(10/5)=2 и ceil(11/5)=3.
Очевидный подход включает что-то как:
q = x / y;
if (q * y < x) ++q;
Это требует дополнительного сравнения и умножения; и другие методы, которые я видел (используемый на самом деле) включают кастинг в качестве a float или double. Существует ли более прямой метод, который избегает дополнительного умножения (или второе подразделение) и ответвление, и это также старается не снимать в качестве числа с плавающей точкой?
4 ответа
Для положительных чисел
unsigned int x, y, q;
Чтобы округлить ...
q = (x + y - 1) / y;
или (чтобы избежать переполнения в x + y)
q = 1 + ((x - 1) / y); // if x != 0
Вы можете использовать функцию div в cstdlib, чтобы получить частное и остаток за один вызов, а затем обработать потолок отдельно, как показано ниже
#include <cstdlib>
#include <iostream>
int div_ceil(int numerator, int denominator)
{
std::div_t res = std::div(numerator, denominator);
return res.rem ? (res.quot + 1) : res.quot;
}
int main(int, const char**)
{
std::cout << "10 / 5 = " << div_ceil(10, 5) << std::endl;
std::cout << "11 / 5 = " << div_ceil(11, 5) << std::endl;
return 0;
}
Ответ Спарки - один из стандартных способов решения этой проблемы, но, как я также писал в своем комментарии, вы рискуете переполниться. Эту проблему можно решить, используя более широкий тип, но что, если вы хотите разделить long long s?
Ответ Натана Эрнста предлагает одно решение, но оно включает вызов функции, объявление переменной и условное обозначение , что делает его не короче, чем код OPs, и, вероятно, даже медленнее, потому что его сложнее оптимизировать.
Мое решение таково:
q = (x % y) ? x / y + 1 : x / y;
Он будет немного быстрее, чем код OP, потому что деление по модулю и деление выполняется с использованием одной и той же инструкции на процессоре, потому что компилятор видит, что они эквивалентны. По крайней мере, gcc 4.4.1 выполняет эту оптимизацию с флагом -O2 на x86.
Теоретически компилятор может встроить вызов функции в код Натана Эрнста и выдать то же самое, но gcc этого не сделал, когда я его тестировал. Это может быть связано с тем, что скомпилированный код будет привязан к одной версии стандартной библиотеки.
И последнее замечание: все это не имеет значения на современной машине, за исключением случаев, когда вы находитесь в чрезвычайно узком цикле, и все ваши данные находятся в регистрах или L1-кэше. В противном случае все эти решения будут одинаково быстрыми, за исключением, возможно, решения Натана Эрнста, который может быть значительно медленнее, если функция должна быть извлечена из основной памяти.
Как насчет этого? (требует неотрицательного значения y, поэтому не используйте это в редких случаях, когда y является переменной без гарантии неотрицательности)
q = (x > 0)? 1 + (x - 1)/y: (x / y);
Я уменьшил y / y до единицы, исключив термин x + y - 1 и с ним возможны переполнения.
Я избегаю обертывания x - 1 , когда x является беззнаковым типом и содержит ноль.
Для подписанного x отрицательное значение и ноль по-прежнему объединяются в один регистр.
Вероятно, это не большое преимущество для современного ЦП общего назначения, но это будет намного быстрее во встроенной системе, чем любой другой правильный ответ.