Быстрый потолок целочисленного деления в C / C ++

Question

При заданных целочисленных значениях x и y, C и C ++ возвращают как частное q = x/y пол эквивалента с плавающей запятой. Меня интересует метод возврата потолка. Например, ceil(10/5)=2 и ceil(11/5)=3.

Очевидный подход включает в себя что-то вроде:

q = x / y;
if (q * y < x) ++q;

Это требует дополнительного сравнения и умножения; и другие методы, которые я видел (использовал на самом деле), включают приведение типа float или double. Есть ли более прямой метод, который избегает дополнительного умножения (или второго деления) и ветвления, и который также предотвращает приведение к числу с плавающей запятой?

Answer 1

для положительных чисел

unsigned int x, y, q;

Округлить ...

q = (x + y - 1) / y;

или (избегая переполнения в x + y)

q = 1 + ((x - 1) / y); // if x != 0

Answer 2

Для положительных чисел:

    q = x/y + (x % y != 0);

Answer 3

Ответ Спарки - это один из стандартных способов решения этой проблемы, но, как я уже писал в своем комментарии, вы рискуете переполниться. Эту проблему можно решить, используя более широкий тип, но что, если вы хотите разделить long long s?

Ответ Натана Эрнста дает одно решение, но оно включает вызов функции, объявление переменной и условное выражение, что делает его не короче кода OP и, возможно, даже медленнее, поскольку его сложнее оптимизировать.

Мое решение таково:

q = (x % y) ? x / y + 1 : x / y;

Это будет немного быстрее, чем код OP, потому что по модулю и делению выполняется одна и та же инструкция на процессоре, потому что компилятор может видеть, что они эквивалентны. По крайней мере, gcc 4.4.1 выполняет эту оптимизацию с флагом -O2 на x86.

Теоретически, компилятор может встроить вызов функции в код Натана Эрнста и выдать то же самое, но gcc не сделал этого, когда я тестировал его. Это может быть связано с тем, что скомпилированный код будет привязан к одной версии стандартной библиотеки.

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

Answer 4

Вы можете использовать функцию 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;
}

Answer 5

Как насчет этого? (требуется y неотрицательный, поэтому не используйте его в редком случае, когда y - переменная без гарантии неотрицательности)

q = (x > 0)? 1 + (x - 1)/y: (x / y);

Я уменьшил y/y до единицы, исключив термин x + y - 1 и, следовательно, шанс переполнения.

Я избегаю x - 1 обтекания, когда x является типом без знака и содержит ноль.

Для x со знаком минус и ноль по-прежнему объединяются в один регистр.

Вероятно, не большое преимущество для современного процессора общего назначения, но это будет гораздо быстрее во встроенной системе, чем любой другой правильный ответ.

Answer 6

Существует решение как для положительного, так и для отрицательного x, но только для положительного y только с 1 делением и без ответвлений:

int ceil(int x, int y) {
    return x / y + (x % y > 0);
}

Обратите внимание: если x положительно, то деление приближается к нулю, и мы должны добавить 1, если напоминание не равно нулю.

Если x отрицательно, то деление к нулю, это то, что нам нужно, и мы ничего не добавим, потому что x % y не является положительным

Answer 7

Это работает для положительных или отрицательных чисел:

q = x / y + ((x % y != 0) ? !((x > 0) ^ (y > 0)) : 0);

Если есть остаток, проверяется, имеют ли x и y одинаковый знак, и добавляет 1 соответственно.

Answer 8

упрощенная универсальная форма,

int div_up(int n, int d) {
    return n / d + (((n < 0) ^ (d > 0)) && (n % d));
} //i.e. +1 iff (not exact int && positive result)

Для более общего ответа C ++ функции для целочисленного деления с четко определенной стратегией округления

Answer 9

Я бы скорее прокомментировал, но у меня недостаточно высокая репутация.

Насколько мне известно, для + ve & pow из 2 это самый быстрый способ (проверено в CUDA)

//example y=8
q = x >> 3 + !!(x & 7);

в противном случае (также + только ve) я бы сделал это так:

q = x/y + !!(x % y);

Answer 10

Компиляция с O3, Компилятор хорошо выполняет оптимизацию.

q = x / y;
if (x % y)  ++q;