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

Question

Быстрый потолок целочисленного деления в 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;

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

357

c++ c algorithm math

Источник

user248123 30 апр '10 в 14:16

11 ответов

Решение

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

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

135

Источник

user2072673 14 фев '13 в 15:52

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

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

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

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

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

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

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

66

Источник

user108517 30 апр '10 в 15:42

Вы могли бы использовать 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;
}

26

Источник

user311314 30 апр '10 в 14:39

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

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

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

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

15

Источник

user768110 13 июн '15 в 23:06

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

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

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

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

Для подписи x, отрицательный и ноль все еще объединяются в одном случае.

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

12

Источник

user103167 30 апр '10 в 22:54

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

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

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

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

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

9

Источник

user5496117 11 фев '19 в 03:08

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

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

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

5

Источник

user3421799 14 мар '14 в 22:45

Для всех целых чисел C++, знаковых / беззнаковых делимых и / или делителей, деления и по модулю, верхнего, нижнего или усеченного. Надеюсь, полный набор операций лучше демонстрирует поведение.

      template <typename Factor1, typename Factor2>
bool negative(Factor1 factor1, Factor2 factor2)
{
    return (factor1 < 0) != (factor2 < 0);
}

template <typename Dividend, typename Divisor>
bool remainder(Dividend dividend, Divisor divisor)
{
    return (dividend % divisor) != 0;
}

template <typename Dividend, typename Divisor>
Dividend ceilinged_modulo(Dividend dividend, Divisor divisor)
{
    // No change unless remainder, and c++ mod ceilinged for negative quotient.
    return !remainder(dividend, divisor) || negative(dividend, divisor) ?
        truncated_modulo(dividend, divisor) :
        divisor + truncated_modulo(dividend, divisor);
}

template <typename Dividend, typename Divisor>
Dividend floored_modulo(Dividend dividend, Divisor divisor)
{
    // No change unless remainder, and c++ mod floored for positive quotient.
    return !remainder(dividend, divisor) || !negative(dividend, divisor) ?
        truncated_modulo(dividend, divisor) :
        divisor - truncated_modulo(-dividend, divisor);
}

template <typename Dividend, typename Divisor>
Dividend truncated_modulo(Dividend dividend, Divisor divisor)
{
    // C++ applies "toward zero" integer division rounding (and remainder).
    // Floored for positive quotient, ceilinged for negative quotient.
    return dividend % divisor;
}

template <typename Dividend, typename Divisor>
Dividend ceilinged_divide(Dividend dividend, Divisor divisor)
{
    // No change unless remainder, and c++ div ceilinged for negative quotient.
    return !remainder(dividend, divisor) || negative(dividend, divisor) ?
        truncated_divide(dividend, divisor) :
        truncated_divide(dividend, divisor) + 1;
}

template <typename Dividend, typename Divisor>
Dividend floored_divide(Dividend dividend, Divisor divisor)
{
    // No change unless remainder, and c++ div floored for positive quotient.
    return !remainder(dividend, divisor) || !negative(dividend, divisor) ?
        truncated_divide(dividend, divisor) :
        truncated_divide(dividend, divisor) - 1;
}

template <typename Dividend, typename Divisor>
Dividend truncated_divide(Dividend dividend, Divisor divisor)
{
    // C++ applies "toward zero" integer division rounding (and remainder).
    // Floored for positive quotient, ceilinged for negative quotient.
    return dividend / divisor;
}

4

Источник

user1172329 16 май '21 в 17:21

Упрощенная общая форма,

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++ для целочисленного деления с четко определенной стратегией округления

3

Источник

user4553834 18 ноя '15 в 21:25

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

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

-2

Источник

user9827423 09 июн '19 в 09:27

Другие вопросы по тегам c++ c algorithm math

user251020 30 апр '10 в 14:19 2010-04-30 14:19 · Accepted Answer · 2010-04-30 14:19

Чтобы округлить...

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

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

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

529

Источник

user251020 30 апр '10 в 14:19